动态规划

动态规划求解规律：

动态规划能解决的问题，需要满足“一个模型三个特征”。

一个模型

• 多阶段决策最优解模型

动态规划能解决的问题都可以抽象成“多阶段决策最优解模型”。即求解问题的过程可以分为多个阶段，每个阶段对应多个状态，从所有阶段状态中选择一组最优解序列，可以得到所求。

三个特征

• 最优子结构：

  问题的最优解，可以通过子问题的最优解求得。

• 无后效性：

  求解当前阶段的状态时，只需关心前一阶段的状态，而不需要关心前一阶段的状态怎么来的；

  前阶段的状态一旦确定，就不再受后阶段决策的影响。

• 重复子问题：

  不同决策序列，到达某一状态时，会产生重复解。

动态规划求解方法

• 状态转移表法

  能用动态规划求解的问题，都可以用回溯法暴力求解。

  一般求解步骤为：

  • 回溯法暴力求解；

  • 画状态树；

  • 确定重复子问题（确定是否符合动态规划特征）；

  • 画状态转移表；

  • 确定每个阶段的状态；

  • 翻译成代码。

• 状态转移方程法

  一般求解步骤为：

  • 找最优子结构；

  • 确定动态转移方程；

  • 翻译成代码：递归加备忘录；或者迭代递推。