分类：
2009-03-07 22:20:21
动态规划把一个问题看成一系列相互关联的子问题，子问题再分成更小的问题，小的子问题的解决导致大子问题的解决，最终解决整个问题。
动态规划算法设计可以分为如下4个步骤：
1. 描述最优解的结构。可以遵循一种共同的模式：
a)问题的解可以是做一个选择，做这种选择会得到一个或者多个有待解决的子问题
b)不必关心如何确定这个选择是最优选择，尽管假设是已知最优的
c)在已知这个选择后，要确定哪些子问题会随之发生，以及如何最好的描述所得到的子问题空间
d)证明在问题的一个最优解中，使用的子问题的解本身也是最优的。假设不是最优的，然后导出矛盾
2.递归定义最优解的值，写出递归定义式
3.按自底向上的方式计算最优解的值。
具体操作方式，从i=1...n计算递归式的值，记录每一步的结果值以供下次循环使用，同时记录一些附加信息用来构造最优解
4.构造最优解
经典问题：装配线调度、矩阵链乘法、最长公共子序列、最优二叉查找树
