我假设你已经阅读了维基百科和其他关于这方面的学术资源，所以我不会重复使用任何信息。我还必须提醒，我不是计算机科学专家，但我将分享我对这些主题的理解……

动态规划

把问题分解成离散的子问题。Fibonacci序列的递归算法是动态规划的一个例子，因为它通过首先求解fib(n-1)来求解fib(n)。为了解决原来的问题，它解决了一个不同的问题。

分而治之

These algorithms typically solve similar pieces of the problem, and then put them together at the end. Mergesort is a classic example of divide and conquer. The main difference between this example and the Fibonacci example is that in a mergesort, the division can (theoretically) be arbitrary, and no matter how you slice it up, you are still merging and sorting. The same amount of work has to be done to mergesort the array, no matter how you divide it up. Solving for fib(52) requires more steps than solving for fib(2).

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

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

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之间的区别。

分治法在每一级递归中涉及三个步骤:

把问题分成子问题。 通过递归求解子问题来克服子问题。 将子问题的解合并到原问题的解中。 这是一种自顶向下的方法。 它在子问题上做更多的工作，因此有更多的时间 消费。 如。斐波那契数列的第n项可以用O(2^n)个时间复杂度计算。

动态规划包括以下四个步骤: 1. 描述最优解的结构。 2. 递归地定义最优解的值。 3.计算最优解的值。 4. 从计算的信息构造一个最优解。

这是一种自底向上的方法。 由于我们使用了之前计算的值，而不是再次计算，因此比分治算法花费的时间更少。 如。斐波那契数列的第n项可以用O(n)个时间复杂度来计算。

为了便于理解，让我们将分而治之视为一种暴力解决方案，并将其优化视为动态规划。 注意:具有重叠子问题的分治算法只能用dp进行优化。

分而治之 它们分解成互不重叠的子问题 示例:阶乘数，即fact(n) = n*fact(n-1)

fact(5) = 5* fact(4) = 5 * (4 * fact(3))= 5 * 4 * (3 *fact(2))= 5 * 4 * 3 * 2 * (fact(1))

正如我们上面看到的，没有事实(x)是重复的，所以阶乘没有重叠的问题。

动态规划 他们分成了重叠的子问题 示例:斐波那契数列，即fib(n) = fib(n-1) + fib(n-2)

fib(5) = fib(4) + fib(3) = (fib(3)+fib(2)) + (fib(2)+fib(1))

如上所述，fib(4)和fib(3)都使用fib(2)。同样的，很多fib(x)被重复。这就是为什么斐波那契有重叠的子问题。

由于DP中子问题的重复，我们可以将这些结果保存在一个表中，节省了计算量。这被称为记忆

分而治之

在此问题的解决分为以下三步: 1. 划分-划分若干个子问题 2. 征服——通过递归解决子问题来征服 3.组合-结合子问题的解决方案，以得到原问题的解决方案 递归方法 自顶向下技术 示例:归并排序

动态规划

在此问题的解决步骤如下: 1. 定义最优解的结构 2. 反复定义最优解的值。 3.用自底向上的方法求最优解的值 4. 从得到的值得到最终的最优解 非递归 自底向上技术 例子:Strassen矩阵乘法

分而治之:

这一范式包括三个阶段:

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

动态规划:

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)