三个特征

• 最优子结构

  问题最优解包含子问题的最优解，即可以通过子问题得到最优解。

• 无后效性

  有两层含义：

  1. 在后面的推到过程中，只关心前面的状态值，不关心这个状态是怎么一步步推导出来的。
  2. 前面的状态如果已经确定，就不会收到后面状态影响

• 子问题重叠

  不同的决策序列，到达某个相同的阶段是，可能产生重复的状态

方法

1. 状态转移法

   首先，使用搜索。

   其次，画出递归树。

   最后，看是否存在重复子问题，以及重复子问题是如何产生的，以此寻找规律，看能否用 DP 解决

2. 状态转移方程法

   分析某个子问题如何通过子问题递归求解，以此来写转移方程

参考文章