分治算法与动态规划的区别

分治算法和动态规划算法的区别是什么?这两个术语有什么不同?我不明白它们之间的区别。

请举一个简单的例子来解释两者之间的区别，以及它们相似的理由。

当前回答

分而治之:

这一范式包括三个阶段:

把这个问题分成更小的子问题征服，即解决这些较小的子问题结合这些子问题的解，得到最终答案。

动态规划:

DP is an optimization of recursive solutions. The primary difference it makes is that it stores the solution to sub-problems, which can later be accessed during the process of finding solutions of the remaining sub-problems. This is done so that we don't have to calculate the solution to a sub-problem every time, rather we can simply look it up the computer memory to retrieve its value, given that it has been solved earlier. We can simply add this as our base case in recursion. For example, we are solving a problem through recursion, we can store the solutions to sub-problems in an array and access them by adding the relevant code in one of our base cases in the recursive method.

DP有两种实现方式:

考虑一个问题:求x的阶乘。

制表法:我们使用自底向上的方法，也就是从最小的数一直到x，来找到解。

伪代码:

 1. int array
 2. for int=1, i<=x, i++
 3. array[i] = array[i-1]*i

记忆法:我们使用自顶向下的方法，也就是说，我们把问题分解成更小的部分，然后解决它们，以得到最终的解决方案

伪代码:

 fac():
 1. int array
 2. if(x==0): return 1
 3. if(array[x]!=null): return array[x]
 4. return array[x] = x*fac(x-1)

2022-12-03 08:47:18

其他回答

有时候在递归编程时，你会多次调用具有相同参数的函数，这是不必要的。

著名的斐波那契数列例子:

           index: 1,2,3,4,5,6...
Fibonacci number: 1,1,2,3,5,8...

function F(n) {
    if (n < 3)
        return 1
    else
        return F(n-1) + F(n-2)
}

我们运行F(5):

F(5) = F(4) + F(3)
     = {F(3)+F(2)} + {F(2)+F(1)}
     = {[F(2)+F(1)]+1} + {1+1}
     = 1+1+1+1+1

所以我们叫: 1乘以F(4) 2乘以F(3) 3乘以F(2) 2乘以F(1)

动态编程方法:如果多次调用具有相同参数的函数，则将结果保存到变量中，以便下次直接访问。迭代方法:

if (n==1 || n==2)
    return 1
else
    f1=1, f2=1
    for i=3 to n
         f = f1 + f2
         f1 = f2
         f2 = f

我们再次调用F(5):

fibo1 = 1
fibo2 = 1 
fibo3 = (fibo1 + fibo2) = 1 + 1 = 2
fibo4 = (fibo2 + fibo3) = 1 + 2 = 3
fibo5 = (fibo3 + fibo4) = 2 + 3 = 5

如您所见，每当您需要多重调用时，您只需访问相应的变量来获得值，而不是重新计算它。

顺便说一下，动态规划并不意味着将递归代码转换为迭代代码。如果需要递归代码，还可以将子结果保存到变量中。在这种情况下，这种技术被称为记忆。在我们的例子中，它是这样的:

// declare and initialize a dictionary
var dict = new Dictionary<int,int>();
for i=1 to n
    dict[i] = -1

function F(n) {
    if (n < 3)
        return 1
    else
    {
        if (dict[n] == -1)
            dict[n] = F(n-1) + F(n-2)

        return dict[n]                
    }
}

所以与分治法的关系是D&D算法依赖于递归。有些版本会出现“使用相同参数的多个函数调用问题”。搜索“矩阵链乘法”和“最长公共子序列”，寻找需要DP来改进D&D算法的T(n)的例子。

2012-11-24 05:45:55

我认为分治法是递归方法，动态规划是表填充。

例如，归并排序是一种分治算法，因为在每一步中，您将数组分成两部分，递归地在两部分上调用归并排序，然后合并它们。

Knapsack是一种动态规划算法，因为您正在填充表示整个背包子问题的最优解的表。表中的每一项都对应于给定物品1-j的袋子中所能携带的最大重量w。

2012-11-24 05:21:48

分而治之和动态规划的另一个区别是:

分而治之:

在子问题上做更多的工作，因此有更多的时间消耗。分治法中子问题是相互独立的。

动态规划:

只解决一次子问题，然后将其存储在表中。在动态规划中，子问题不是相互独立的。

2013-03-26 12:39:59