有一类问题，可以划分出多个阶段完成，每个阶段又可以分出多种不同的状态（阶段与状态划分）。
搜索的时间复杂度过大。
这类问题当然可以用搜索进行暴力枚举，但是时间复杂度很高，通常是指数级的，无法接受。仔细分析后，我们如果能得出如下结论：
每一阶段需要做出的决策，只取决于之前阶段的情况，与之后阶段的情况无关（无后效性原则）。
那么我们就应该利用这样的性质进行有效剪枝，尽早去掉不需要的子问题集合（即提前判断出一些不可能得出最优解的集合，将它们直接跳过），只保留能够产生最优解的子问题集合，从而大大提高算法效率。
贪心和动态规划（Dynamic Programming，简称 DP）就是解决这类问题的最佳选择。
贪心和动态规划（DP）的区别
贪心是一种通过每一个阶段的最优解就可推出全局最优解的算法，其中每阶段的最优解即为该阶段所有状态的最优解。因此，贪心在每个阶段只需保留一个数（最优解），通常一层循环把所有阶段跑一遍即可。
例如：给定一个 $m\times n$ 的矩阵，从每一行选取一个值，使得总和最大。我们直接采用贪心的思路，将原问题划分为 $m$ 个阶段（每一行为一个阶段），每个阶段的最优解（每一行的最大值）累加到一起，就直接可以导出全局最优解。
但不是所有问题都可以用贪心来解决，例如“数字金字塔”，如果按照贪心算法，则只会选择出一条路线：$13\rightarrow 11\rightarrow 12\rightarrow 14\rightarrow 13$，结果为 $63$，而答案应该为：$13\rightarrow 8\rightarrow 26\rightarrow 15\rightarrow 24$，得到 $86$。
数字金字塔
原因在于从 $13$ 往下，虽然走 $8$ 不是第一阶段的最优解，却在后面阶段逐步增大，最终成为了全局最优解。
因此，我们说贪心和DP都是全局最优解包含局部最优解，但它们的区别在于，贪心是阶段最优解直接导致全局最优解，而DP是每个阶段中的每个状态的最优解，导致全局最优解，它是比贪心更细粒度的递推，细化到了状态的层面。所以，我们如果通过分析，发现问题是可以划分阶段的，无后效性的，且不能直接用阶段最优解导出全局最优解的，就可以选择DP来完成。
DP 的步骤
DP类题目的设计步骤通常为：
划分阶段
设定每一阶段的状态，以及最终答案需要的状态。
通常是通过答案的需要来设定状态。两种状态通常是一致的，也有些题目需要先设计一个比较好求解（效率高）的状态，最后通过循环或者其他转换得到答案的状态。
设计从上一个阶段的某个状态，到当前阶段的某个状态的转移方程（递推式）
确定转移方程的初值
我们以 01背包问题 为例：
- 划分阶段
按考虑过多少件物品来划分阶段，通常阶段就是第一维，$f[i]$ 即表示考虑了前 $i$ 件物品。
- 设定状态
由于要求的就是最大价值，所以数组的值就应该设为每个状态的最大价值（即每个阶段的每个状态的局部最优解）。那么状态怎么划分呢？再看题目——要求的是不超过重量 $m$ 的最大价值，那么显然我们应该把重量作为一个状态进行划分，于是将重量作为一个状态维度，$f[i][j]$ 表示前 $i$ 件物品，重量不超过 $j$ 时的最大价值，最终答案应该为：$f[n][m]$。
- 状态转移方程
$f[i][j] = f[i-1][?]$，仔细思考不难发现：上一个阶段和这个阶段的最大区别，就在于第 $i$ 件物品，因此，这个状态转移一定是围绕第 $i$ 件物品来考虑的。
关于第 $i$ 件物品的决策只有 $2$ 种：选与不选。因此产生两种结果：
- 不选第 $i$ 件
第 $i$ 个阶段的状态 $j$ 与第 $i-1$ 个阶段的状态 $j$ 一样，$f[i][j] = f[i-1][j];$
- 选第 $i$ 件
加入第 $i$ 件物品前，第 $i-1$ 个阶段的状态应该为 $j-w[i]$，新的状态 $j$ 的价值应该为两者之和，即 $f[i][j] = f[i-1][j-w[i]] + v[i];$
综合以上两种决策，状态 $f[i][j]$ 应在这两种决策中取最大值，即
$f[i][j] = max(f[i-1][j], f[i-1][j-w[i]]+v[i]);$
- 对于第 $1$ 个阶段来说，它的上一个阶段有 $0$ 件物品，任意一个状态的价值都设为 $0$ 即可。
转载请注明来源
