算法设计与分析 (清华大学)第三章 动态规划.ppt

4 动态规划算法的基本要素 一最优子结构 矩阵连乘计算次序问题的最优解包含着其子问题的最优解这种性质称为最优子结构性质 在分析问题的最优子结构性质时所用的方法具有普遍性首先假设由问题的最优解导出的子问题的解不是最优的然后再设法说明在这个假设下可构造出比原问题最优解更好的解从而导致矛盾 利用问题的最优子结构性质以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解最优子结构是问题能用动态规