动态规划（Dynamic Programming）与分治方法相似，都是通过组合子问题的解来求解原问题。分治方法将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题。在这种情况下，分治算法会做许多不必要的工作，它会反复地求解那些公共子子问题。而动态规划算法对每个子子问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子子问题时都重新计算，避免了不必要的重复工作。
——《算法导论》
从动态规划的名字（Dynamic Programming，此处 Programming 指的是表格记录，而非编程）就可看出，表格记录是动态规划的一个关键特征，这也是其与分治法的一个区别。
在分治法中，当父问题被分解为几个子问题后，尽管子问题又被分解为子子问题，但父问题的解仅由子问题的解计算出来，不直接依赖与子子问题。因而我们在得到下一层（子问题）的解后，就不保存下下一层（子子问题）的解了，即用不到表格记录。而在动态规划问题中，比如背包问题，当我们计算容量为 j 的背包时，可能会用到容量为 j - weight[i] 的背包的解，相比于分治的层层分离，这便是动态规划问题的重叠所在。
而且，动态规划是一种通过递归思想自上向下分析问题，而通过循环自下而上解决问题的方法。因为问题的依赖性是上向下依赖，只有自下而上，才有可能实现有效的记忆化。
不同算法应对的场景：
- 子问题最优则原始问题最优——贪心算法或者动态规划算法。
- 子问题最优则原始问题最优，且子问题互相独立——分治算法。
- 子问题最优不能推导出原始问题最优——暴力搜索等。
狭义动态规划 与 广义动态规划 #
- 狭义的动态规划是指使用 dp table，以递推的方式来求解。
- 广义的动态规划可以是备忘录递归，也可以是 dp table 递推。
记忆化搜索（递归） vs 狭义动态规划（递推） #
记忆化搜索是通过记录已经遍历过的状态的信息，从而避免对同一状态重复遍历的搜索实现方式。
因为记忆化搜索确保了每个状态只访问一次，所以它也属于（广义）动态规划。
记忆化搜索与递推的代码，在形式上是高度类似的。这是由于他们使用了相同的状态表示方式和状态转移方程。也正因如此，二者的时间复杂度一般是差不多的（由于需要维护递归栈，记忆化搜索的时间开销会大一些），但是由于使用了递归，其空间复杂度要高得多。
记忆化搜索和递推都确保了同一状态至多只被求解一次，而他们实现这一点的方式略有不同。递推通过设置明确的访问顺序来避免重复访问。而记忆化搜索虽然没有明确的访问顺序，但是通过给已经访问过的子状态打标记的形式，也达到了相同的目的。
- 相同点
- 都有重叠子问题。相对于暴力求解，使用这两种方法的目的，都是为了避免重复计算这些重叠子问题。
- 都有状态（case）、base case 和状态转移方程。
- 区别点
- 记忆化搜索的编程模式是递归，而狭义动态规划（递推 DP） 的编程模式是递推。一般来说，递归的时间和空间开销比递推大。并且递推不一定需要保存所有状态，如 dp[i] = dp[i-1] + dp[i-2] 只需要保存两个状态即可。
- 记忆化搜索是自顶向下求解，从目标状态到边界条件。递推 DP 是自底向上，从边界条件到目标状态。
- 记忆化搜索不需要严格设计好计算顺序，备忘录没有记录则进行计算即可。而递推 DP 则通过严格计算 dp table 的递推计算顺序，来避免重复计算。
- 多个状态下，递推 DP 有可能会产生大量无效状态，而记忆化搜索则不会。这是记忆化搜索在速度上有可能战胜递推 DP 的地方。
回溯 → 记忆化搜索 → 递推 DP 三部曲 #
- step1，回溯：遍历所有状态（可能剪枝）
- step2，记忆化搜索：存下已访问过的状态以避免重复计算
- step3，递推 DP：设置明确的访问顺序来避免重复
形象比喻 #
-
分治
分而治之。先解决子问题，再将子问题的解合并求出原问题。
-
贪心
一条路走到黑。选择当下局部最优路线，没有后悔药。
-
回溯
一条路走到黑，手握后悔药，可以不断折返重来。
-
动规
上帝视角，手握无数个平行宇宙的历史存档，同时发展出无数个未来。