算法导论-动态规划-笔记

动态规划：找其中一个最优解
4个步骤来设计
1.刻画一个最优解的结构特征
2.递归地定义最优解的值
3.计算最优解的值，通常是自底向上的方法
4.构造解

适合用动态规划求解的最优化问题，应具备两个要素：
最优子结构、子问题重叠

对于不同问题领域，最优子结构的不同 体现在两个方面：

1. 原问题的最优解中涉及多少个子问题
2. 在确定最优解使用哪些子问题时，我们需要考察多少种选择

动态规划 vs 贪心算法
能够应用贪心算法的问题也必须具有最优子结构性质。两者不同之处是：
动态规划，首先寻找子问题的最优解，然后在其中选择
贪心算法，首先做一次“贪心”选择————在当时（局部）看来最优的选择————然后求解选出的子问题，从而不必求解所有可能相关的子问题

贪心算法两个关键要素：
贪心选择性质
最优子结构