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

动态规划

把问题分解成离散的子问题。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。

分而治之

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

动态规划

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

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

动态规划

把问题分解成离散的子问题。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).

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

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

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

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

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

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