文章浏览阅读250次。第15章 动态规划定义及原理钢条切割问题最长公共子序列最优二叉搜索树定义及原理动态规划和分治法类似，都是通过组合子问题的解来求解原问题。动态规划应用于子问题重叠的情况，及不同的子问题具有公共的子子问题。在这种情况下，分治法会做许多不必要的工作，重复计算求解那些公共子子问题。而动态规划只求解一次，避免了不必要的工作。我们通常按照下面四个步骤来设置动态规划算法：刻画一个最优解的结构特征递归地定义最优解的值计算最优解的值，通常采用自底向上的方法利用计算出的信息构造一个最优解前三步是动态规划算法_算法导论第十五章笔记