动态规划

1、思考状态（重点）

状态的定义，先尝试，题目问什么，就把什么设置为状态；

然后思考状态如何转移，如果状态转移方程不容易得到，尝试修改定义，目的依然是为了方便得到状态转移方程。

状态转移方程是原始问题的不同规模的子问题的联系。即大问题的最优解如何由小问题的最优解得到。

2、思考状态转移方程（核心、难点）

状态转移方程是非常重要的，是动态规划的核心，也是难点；

常见的推导技巧是：分类讨论。即：对状态空间进行分类；

归纳状态转移方程是一个很灵活的事情，通常是具体问题具体分析；

除了掌握经典的动态规划问题以外，还需要多做题；

如果是针对面试，请自行把握难度。掌握常见问题的动态规划解法，理解动态规划解决问题，是从一个小规模问题出发，逐步得到大问题的解，并记录中间过程；

动态规划方法依然是空间换时间思想的体现，常见的解决问题的过程很像在填表。

3、思考初始化

初始化是非常重要的，一步错，步步错。初始化状态一定要设置对，才可能得到正确的结果。

角度 1：直接从状态的语义出发；

角度 2：如果状态的语义不好思考，就考虑状态转移方程的边界需要什么样初始化的条件；

角度 3：从状态转移方程方程的下标看是否需要多设置一行、一列表示哨兵（sentinel），这样可以避免一些特殊情况的讨论。

4、思考输出

有些时候是最后一个状态ÿ