# 动态规划

**动态规划求解规律：**

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

## 一个模型

* 多阶段决策最优解模型

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

## 三个特征

* 最优子结构：

  问题的最优解，可以通过子问题的最优解求得。
* 无后效性：

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

  前阶段的状态一旦确定，就不再受后阶段决策的影响。
* 重复子问题：

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

## 动态规划求解方法

* 状态转移表法

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

  一般求解步骤为：

  * 回溯法暴力求解；
  * 画状态树；
  * 确定重复子问题（确定是否符合动态规划特征）；
  * 画状态转移表；
  * 确定每个阶段的状态；
  * 翻译成代码。
* 状态转移方程法

  一般求解步骤为：

  * 找最优子结构；
  * 确定动态转移方程；
  * 翻译成代码：递归加备忘录；或者迭代递推。
