动态规划基本原理

  1.  设计多阶段决策过程
  2.  分析最优子结构性质
  3.  建立状态表示和状态转移方程

最优子结构性质

问题的最优解包含其子问题的最优解。也就 是说，如果把问题的最优解分解（比如划分 为两个或者多个部分，或者删除第一个或者 最后一个分量），得到一个子解，那么这个 子解是其相应子问题的最优解。 证明方法（反证法）：

  1. 假设子解不是子问题最优解
  2. 基于子解构造原问题的一个新解
  3. 证明新解是原问题的更好答案，与前提矛盾！

 最优值计算

 状态表示和状态转移方程确定问题解之间的递推关系

 有限个（多项式级别）状态/子问题

 自底向上（由易至难）求解各状态值

构造状态转移方程：

1）原问题最优解划分为多个子解：矩阵连乘

2）原问题最优解约简为一个子解：多段图最短路径、0-1背包

3）对间接目标设计状态转移方程：最大上升子序列