基本思想：将待求解问题分解成若干子问题，先求解子问题，然后从子问题的解中得到原问题的解。
与分治不同的是，经分解得到的子问题往往不是互相独立的。
若用分治法来解这些问题，则得到的子问题数目太多，以至于最后解决原问题需要消耗指数时间。
步骤设计：
1 找出最优解的性质，并刻画其结构特征
2 递归地定义最优值
3 以自底向上的方式计算出最优值
4 根据计算最优值得到的信息，构造最优解
应用实例：
矩阵连乘问题
最长公共子序列
最大子段和
凸多边形最优三角剖分
多边形游戏
图像压缩
电路布线
流水作业调度
背包问题
最优二叉搜索树
本文转自博客园xingoo的博客，原文链接：动态规划，如需转载请自行联系原博主。
