四大基础算法之动态规划算法

和分治法一样，动态规划是通过组合自问难题的解去解决整个问题的。分治法是指将问题划分成一些独立的子问题，递归地求解各子问题，然后合并各子问题的解而得到原问题的解。与此不同，动态规划适用于子问题不是独立问题的情况，也就是各子问题包含公共的子子问题。在这种情况下，用分治法则会做许多不必要的工作，即重复的求解公共的子子问题。动态规划算法对子子问题只求解一次，并将其结果保存在一张表中。从而避免每次遇见子子问题都要重新计算答案。

动态规划通常用于最优化问题。此类问题可能有很多可行解。每个解有一个值，而我们希望找出具有最优（最大或最小）值的解。称这样的解为该问题的“一个”最优解（而不是“确定的”最优解），因为可能存在多个取最优值的解。

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

1. 描述最优解的结构。
2. 递归定义最优解的值。
3. 按自底向上计算最优解的值。
4. 由计算结果构造一个最优解。

第1~3步构成了问题的动态规划解的基础。第4步在只要求计算最优解的值时可以略去。如果明确要做第4步，则有时需要在第3步的计算中记录一些附加信息，使构造一个最优解变得容易。