什么是动态规划(dynamic programming)，其实它与分治法相同，都是通过组合子问题的解来解决整个问题。分治法是把问题划分成一些独立的子问题，递归的求解各个子问题，然后合并子问题的解而得到原问题的解。不同的是，动态规划适用于子问题不是独立的情况，而是各子问题包含公共的子子问题。这种情况下，若用分治法则会重复的求解公共的子子问题。动态规划算法只对每个子子问题求解一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算。

动态规划通常应用于最优化问题。此类问题可能有多种可行解，而使用动态规划可以找出一个最优解。

动态规划算法可分为如下4个步骤：

（1）描述最优解的结构

（2）递归定义最优解的值。

（3）按自底向上的方式计算最优解的值。

（4）由计算出的结果构造一个最优解。

第1~3步构成问题的动态规划解的基础。如果只要求计算最优解的值，那第4步可以省略。

《Introduction to Algorithms》笔记