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

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

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

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

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

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

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

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

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

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

分而治之

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

动态规划

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

分而治之 它们分解成互不重叠的子问题 示例:阶乘数，即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中子问题的重复，我们可以将这些结果保存在一个表中，节省了计算量。这被称为记忆

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

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

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

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

让我们一步一步来……

动态规划先决条件/限制

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

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

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

分而治之的动态规划扩展

动态规划方法通过两种技术(记忆和制表)扩展了分而治之的方法，这两种技术都具有存储和重用子问题解决方案的目的，可以极大地提高性能。例如，斐波那契函数的朴素递归实现的时间复杂度为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之间的区别。

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

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

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