阅读 100

动态规划解题总结

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

解题过程

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

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

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

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

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

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

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

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

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

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

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

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

关注下面的标签,发现更多相似文章
评论