动态规划算法的一般解题思路

**1. 证明优化子结构** 对于问题的优化子结构，给出问题具有优化子结构的解代价，利用反证法，假设上解不是最优的，则存在另外一个解，其解优于上解，这与上解是最优的矛盾，于是该问题具有优化子结构。 证明优化子结构问题主要利用反证法。 **2. 证明重复子问题** 给出问题的递归公式则重叠子问题鍀证。 **3. 递归的定义最优解的代价** 给出最有解的代价递归公式，利于代码编写。 **4. 自底向上计算最优解的代价** 一般利用二维矩阵求解代价，或一行一行计算代价，或按列计算代价，或按照对角线逐级计算代价。 **5. 构造最优解** 根据最有接的代价矩阵信息，编写函数构造最优解。