概述

这里我们引用一下维基百科的描述：“动态规划（Dynamic Programming, DP）在查找有很多 重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问 题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划 保存递归时的结果，因而不会在解决同样的问题时花费时间      动态规划只能应用于有最优 子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能 完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。”通俗一点来讲，动态规划和其它遍历算法（如深/广度优先搜索）都是将原问题拆成多个子问
题然后求解，他们之间最本质的区别是，动态规划保存子问题的解，避免重复计算。解决动态规 划问题的关键是找到状态转移方程，这样我们可以通过计算和储存子问题的解来求解最终问题。 同时，我们也可以对动态规划进行空间压缩，起到节省空间消耗的效果。这一技巧笔者将在 之后的题目中介绍。 在一些情况下，动态规划可以看成是带有状态记录（memoization）的优先搜索。状态记录的 意思为，如果一个子问题在优先搜索时已经计算过一次，我们可以把它的结果储存下来，之后遍 历到该子问题的时候可以直接返回储存的结果。动态规划是自下而上的，即先解决子问题，再解 决父问题；而用带有状态记录的优先搜索是自上而下的，即从父问题搜索到子问题，若重复搜索 到同一个子问题则进行状态记录，防止重复计算。如果题目需求的是最终状态，那么使用动态搜 索比较方便；如果题目需要输出所有的路径，那么使用带有状态记录的优先搜索会比较方便。
DP 高赞回答
非波那契例子过于简单，以至于让人们忽视了阶段的概念，所谓阶段是指随着问题的解决，在同一时刻可能会得到的不同状态的集合。现在问题来了，有了阶段之后，计算新状态可能会遇到各种奇葩的情况，针对不同的情况，就需要不同的算法，下面就分情况来说明一下：
假如问题有 n 个阶段，每个阶段有多个状态，不同阶段的状态数不必相同，一个阶段的一个状态可以得到下个阶段的所有状态中的几个。那我们要计算出最终阶段的状态数自然要经历之前每个阶段的某些状态。
既然问题都是可以划分成阶段和状态的。这样一来我们一下子解决了一大类问题：一个阶段的最优可以由前一个阶段的最优得到。
如果一个阶段的最优无法用前一个阶段的最优得到呢？

再来一个迷宫的例子。在计算从起点到终点的最短路线时，你不能只保存当前阶段的状态，因为题目要求你最短，所以你必须知道之前走过的所有位置。因为即便你当前再的位置不变，之前的路线不同会影响你的之后走的路线。这时你需要保存的是之前每个阶段所经历的那个状态，根据这些信息才能计算出下一个状态！
每个阶段的状态或许不多，但是每个状态都可以转移到下一阶段的多个状态，所以解的复杂度就是指数的，因此时间复杂度也是指数的。哦哦，刚刚提到的之前的路线会影响到下一步的选择，这个令人不开心的情况就叫做有后效性。
刚刚的情况实在太普遍，解决方法实在太暴力，有没有哪些情况可以避免如此的暴力呢？
契机就在于后效性。

所以一个问题是该用递推、贪心、搜索还是动态规划，完全是由这个问题本身阶段间状态的转移方式决定的！
每个阶段只有一个状态->递推；
每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心；
每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索；
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到
这个性质叫做最优子结构；
而不管之前这个状态是如何得到的
这个性质叫做无后效性。

描述

动态规划问题的一般形式就是求最值。其实它是运筹学的一种最优化方法，比如让你求最长递增子序列、最小编辑距离等。
求最值的核心问题就是穷举。
动态规划的穷举是很有特点的：

  1. 这类问题存在重叠子问题。如果暴力穷举效率低下，所以需要备忘录或 DP table 来优化穷举过程，避免不必要的重复计算。
  2. 动态规划问题一定会具备最优子结构。这样才能通过子问题的最值得到原问题的最值。
  3. 需要列出正确的状态转移方程。

以上三点就是动态规划的三要素。在实际的算法问题中，写出状态转移方程是最困难的。不过，遵循以下步骤可以辅助你思考并写出正确的状态转移方程：

  1. 明确状态。
  2. 定义 DP 数组/函数的含义。
  3. 明确选择。
  4. 明确 Base Case。

这里还有些文件提出无后效性的概念，它有两层含义：

  1. 在推导后面阶段状态时，我们只关心前面阶段的状态值，不关心这个状态的推导过程。
  2. 某阶段状态一旦确定，就不受之前阶段的决策影响。

斐波那契数列和凑零钱问题都是了解和学习动态规划的好问题。

  1. int fib(int n) {
  2.     if (n == 1 || n == 2) return 1;
  3.     return fib(n - 1) + fib(n-2);
  4. }

通过递归树，发现算法非常低效，比如 f(18) 被计算了两次。这就体现了可以使用动态规划的特性之一：重叠子问题。
可以使用带备忘录的递归解法，我们可以使用一个备忘录将已计算好的结果存起来，每次遇到了个子问题就先去备忘录里查一查，如果发现，直接把答案拿出来用，不用再耗时计算。一般使用一个数组或哈希表充当备忘录。

递归的时间复杂度：子问题个数乘以解决一个子问题需要的时间。

使用动态规划是自底向上过程。
凑零钱问题可以体现最优子结构特性。
要符合最优子结构，子问题必须互相独立。回到凑零钱问题，为什么说它符合最优子结构呢? 比如你想求 amount=11 时的最少硬币数（原问题），如果你知道凑出 amount=10 的最小硬币数（子问题），你只需要把子问题的答案加 1（再选一枚面值为 1 的硬币）就是原问题的答案，因为硬币的数量是没有限制的，子问题之间没有相互限制，是互相独立的。