mooc动态规划学习记录

• 关于动态规划学习的总结：(来源：https://www.icourse163.org/learn/NJTU-1003359012?tid=1450192445#/learn/content?type=detail&id=1214347154&cid=1217939319)
• • 课件4.14小结

动态规划基本原理

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

最优子结构性质

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

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

 最优值计算

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

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

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

构造状态转移方程：

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

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

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