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

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

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

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

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

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

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

标签: none

添加新评论