动态规划(Dynamic Programming) 和 贪心算法(Greedy Algorithm) 都常用来解决最优化问题(Optimization problem)，这类问题有许多可行解，每个解都有一个值，希望寻找具有最优值的解，此解往往是一个最优解，而不是最优解，因为可能有多个解都能使问题达到最优值。
动态规划和贪心算法在求解过程上有区别，但也有联系，比如求解的问题都要满足最优子结构(Optimal Substructure)性质。
最优子结构性质：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。
动态规划
动态规划和分治方法相似，都是通过组合子问题的解来求解原问题。不同的是，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题。此时，动态规划对每个子子问题只会求解一次，并在表中保存，可以避免不必要的重复计算。
问题要素：最优子结构性质，子问题重叠性质
基本设计步骤
- 刻画一个最优解的结构特征，即最优子结构特征。
- 递归地定义最优解的值，得到状态转移方程（递归表达式）。
- 计算最优解的值，通常有两种方法：带备忘的自顶向下法(top-down with memoization)和自底向上法(bottom-up method)。
- 利用计算出来的信息构造一个最优解。
最优子结构
刻画最优子结构通常遵循如下的通用模式：
- 证明问题最优解的第一个组成部分是做出一个选择，这便产生一个或多个待解的子问题。
- 对于一个给定问题，在其可能的第一步选择中，假定已经知道哪种选择才会得到最优解。但现在不关心选择是如何得到的，只假定已经知道了这种选择。
- 给定可获得最优解的选择后，确定这次选择会产生哪些子问题，以及如何更好地刻画子问题空间。
- 利用“剪切-粘贴”(cut-and-paste)技术证明：作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。证明这一点常采用反证法。
子问题重叠
子问题重叠性质要求，利用动态规划方法求解最优解过程中，递归算法会反复求解相同的子问题，而不是不停地生成新的子问题。这也是动态规划和分治方法求解中的一个区别。
贪心算法
贪心算法在求解的每一步都做出局部的贪心选择，寄希望这样的选择能够产生全局最优解。值得注意的是，贪心算法并不保证得到最优解，但针对很多问题确实能得到最优解。
问题要素：最优子结构性质，贪心选择性质。
基本设计步骤
- 将最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解。
- 证明做出最优选择后，原问题总是存在最优解，即贪心选择总是安全的。
- 证明做出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。
贪心选择性质
贪心选择性质(greedy-choice property): 可以通过做出局部最优（贪心）选择来构造全局最优解。
常见问题与算法
- 贪心算法典型的用来解决的问题，包括活动选择问题，分数背包问题。
- 基于贪心方法设计的算法，包括Huffman编码，单源最短路径的Dijsktra算法，最小生成树(minimum-spanning-tree)算法，(Kruskal算法和Prim算法)。
动态规划与贪心算法的区别和联系
- 动态规划与贪心算法求解的问题都必须具备最优子结构性质。
- 贪心算法本质上是对动态规划的优化，对每个用贪心算法求解的问题，几乎也存在一个动态规划的解法。
- 动态规划方法中，每个步骤要进行一次选择，但选择通常依赖于子问题的解，因此通常使用自底向上的方法，先求解较小子问题，再根据子问题的解做出选择。而贪心算法在进行第一次选择之前不求解任何子问题，通常采用自顶向下的方法，进行一次又一次选择，将给定问题实例变小。