动态规划解题总结

发现动态规划算法经常在秋招的笔试题中碰到，那么就一定要对动态规划尽量熟练运用，并且要熟练的写出代码。做了几道题，感觉可以做个总结。

解题过程

1. 看题分析题目是否存在重复子问题

动态规划的原理就是需要解决的问题存在重复的子问题，因此可以像递归那样从最简单的子情况开始，逐渐推导出更大规模的问题的解法，每一步的解既是从前一个子解推导得到，同时又根据它推导到更大的问题。

2. 分析子问题和当前问题的转换关系，写出状态转移方程

这里是最困难的一步，也是最关键的一步。这需要去发现当前问题和其子问题的关系。很像数学里的归纳推导里的根据前一项计算后一项的结果。

3. 根据上一步的分析，可以新建一个表dp用来存储在推导过程中的每一项的结果，以便计算下一项的时候可以直接从表里获得子问题的解，而不用重新计算子问题。

这个表的建立其实也是动态规划提高效率的关键。因为当碰到当前问题的时候就不要重新计算子问题，而是直接从表里查找子问题的解，从而提高时间复杂度的效率。dp有可能是一维乃至多维的，一维的情况通常是初始化最简单的情况，然后向后推导，从前向后初始化dp。而当dp是二维的时候，在初始化了最简单的情况，需要根据，子问题向后拓展的顺序去初始化dp矩阵。

4. 把初始化和向后推导的顺序转换成相应的代码表示

初始化一般比较简单。向后推导的过程转换成dp的赋值操作则稍微复杂一些。这个过程主要还是依赖于推导下一项的过程，体现在代码上，是循环操作。

5. 循环里写上状态转移方程

如果外层循环保证写对的情况下且状态转移方程已经写好，那么这一步代码写起来就会很简单，只需要把状态转移方程写成代码的形式即可。但是需要注意的是，外层循环控制着赋值的顺序，要保证计算当前项的时候，他所需要的子问题的解已经写到dp里了。这就需要外层循环的写法要对。

6. 写完以后用一个简单的例子，模拟整个过程，看循环的过程是否正确，状态方程有没有问题

这一步只需要自己设计一个简单的测试用例，主要检查状态方程对不对，还有循环赋值的循序对不对。