第四章算法设计与分析-动态规划(8)

动态规划算法的基本要素： 一、最优子结构(即最优化原理): 特征：当要求一个问题的最优解时，构成整体解的子问 题的解也必须是最优的。 矩阵连乘计算次序问题的最优解包含着其子问题的最优 解。这种性质就是最优子结构性质。在分析问题的最优子结构 性质时，所用的方法具有普遍性：首先假设由问题的最优解导 出的子问题的解不是最优的，然后再设法说明在这个假设下可 构造出比原问题最优解更好的解，从而导致矛盾。 利用问题 的最优子结构性质，以自底向上的方式递归地从子问题的最优 解逐步构造出整个问题的最优解。最优子结构是问题能用动态 规划算法求解的前提。12/14/2012 6:50 PM 8