动态规划

基本思想：将待求解问题分解成若干子问题，先求解子问题，然后从子问题的解中得到原问题的解。

与分治不同的是，经分解得到的子问题往往不是互相独立的。

若用分治法来解这些问题，则得到的子问题数目太多，以至于最后解决原问题需要消耗指数时间。

步骤设计：

1 找出最优解的性质，并刻画其结构特征

2 递归地定义最优值

3 以自底向上的方式计算出最优值

4 根据计算最优值得到的信息，构造最优解

应用实例：

矩阵连乘问题

最长公共子序列

最大子段和

凸多边形最优三角剖分

多边形游戏

图像压缩

电路布线

流水作业调度

背包问题

最优二叉搜索树