比较“分治法”和“动态规划法”的异同点和优缺点

2024-12-01 07:54:56

推荐回答（2个）

回答1：

共同点：
将待求解的问题分解成若干子问题，先求解子问题，然后再从这些子问题的解得到原问题的解。
不同点：
1、适合于用动态规划法求解的问题，分解得到的各子问题往往不是相互独立的；
而分治法中子问题相互独立。
2、动态规划法用表保存已求解过的子问题的解，再次碰到同样的子问题时不必重新求解，而只需查询答案，故可获得多项式级时间复杂度，效率较高；
而分治法中对于每次出现的子问题均求解，导致同样的子问题被反复求解，故产生指数增长的时间复杂度，效率较低。

回答2：

/*简单算法: **v[0]不保存数据 **T(n)=O(n^2). */ int MaxSum(int *v,int n,int *besti,int *bestj) { int su