分而治之

分而治之的工作原理是将问题划分为子问题，递归地征服每个子问题，并将这些解决方案组合起来。

动态规划

动态规划是一种解决具有重叠子问题的问题的技术。每个子问题只解决一次，每个子问题的结果存储在一个表中(通常实现为数组或哈希表)，以供将来引用。这些子解可以用来获得原始解，存储子问题解的技术称为记忆。

你可能会想到DP =递归+重用

理解差异的一个经典例子是，这两种方法都可以获得第n个斐波那契数。看看麻省理工学院的材料。

分而治之法

动态规划方法

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

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

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

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

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

           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)的例子。

分而治之

分而治之的工作原理是将问题划分为子问题，递归地征服每个子问题，并将这些解决方案组合起来。

动态规划

动态规划是一种解决具有重叠子问题的问题的技术。每个子问题只解决一次，每个子问题的结果存储在一个表中(通常实现为数组或哈希表)，以供将来引用。这些子解可以用来获得原始解，存储子问题解的技术称为记忆。

你可能会想到DP =递归+重用

理解差异的一个经典例子是，这两种方法都可以获得第n个斐波那契数。看看麻省理工学院的材料。

分而治之法

动态规划方法

动态规划与分治的相似之处

在我看来，现在我可以说动态规划是分而治之的范例的扩展。

我不会把它们视为完全不同的东西。因为它们都是通过递归地将一个问题分解为两个或多个相同或相关类型的子问题，直到它们变得足够简单可以直接解决。然后将子问题的解组合起来给出原始问题的解。

那么为什么我们仍然有不同的范式名称，为什么我称动态规划为扩展。这是因为只有当问题具有一定的限制条件或先决条件时，才可以应用动态规划方法。在此基础上，动态规划利用记忆法和制表法对分治法进行了扩展。

让我们一步一步来……

动态规划先决条件/限制

正如我们刚刚发现的，为了使动态规划适用，分治问题必须具有两个关键属性:

最优子结构-最优解可以由其子问题的最优解构造 重叠子问题——问题可以分解为多次重用的子问题，或者问题的递归算法可以一遍又一遍地解决相同的子问题，而不是总是生成新的子问题

一旦满足这两个条件，我们就可以说这个分治问题可以用动态规划方法来解决。

分而治之的动态规划扩展

动态规划方法通过两种技术(记忆和制表)扩展了分而治之的方法，这两种技术都具有存储和重用子问题解决方案的目的，可以极大地提高性能。例如，斐波那契函数的朴素递归实现的时间复杂度为O(2^n)，而DP解决方案只需要O(n)时间就可以完成同样的工作。

记忆(自顶向下缓存填充)是指缓存和重用先前计算结果的技术。因此，记忆fib函数看起来像这样:

memFib(n) {
    if (mem[n] is undefined)
        if (n < 2) result = n
        else result = memFib(n-2) + memFib(n-1)
        
        mem[n] = result
    return mem[n]
}

制表(自底向上的缓存填充)与此类似，但重点是填充缓存的条目。计算缓存中的值最简单的方法是迭代。fib的制表版本是这样的:

tabFib(n) {
    mem[0] = 0
    mem[1] = 1
    for i = 2...n
        mem[i] = mem[i-2] + mem[i-1]
    return mem[n]
}

你可以在这里读到更多关于记忆和制表比较的内容。

这里您应该掌握的主要思想是，由于我们的分治问题具有重叠的子问题，因此可以缓存子问题的解决方案，从而实现记忆/制表。

那么到底DP和DC有什么区别呢

既然我们现在已经熟悉了DP的先决条件和它的方法，我们就可以把上面提到的所有内容放在一张图中了。

如果你想看代码示例，你可以看看这里更详细的解释，你会发现两个算法示例:二进制搜索和最小编辑距离(Levenshtein Distance)，它们说明了DP和DC之间的区别。

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

分而治之:

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

动态规划:

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