动态规划问题总结
本文提纲参考自视频:https://www.bilibili.com/video/av9379437/#page=29
感谢左大神的讲解
文章是本人的学习笔记,侵删!
在介绍动态规划是什么之前,先来看一道题目
求解该题,有四种方法
在面试题中出现类似的题目,优化轨迹高度一致。
方法一:暴力搜索方法
暴力搜索的时间复杂度很高,因为存在太多的重复劳动
方法二:记忆搜索法
其实记忆化搜索的方法,本质上与动态规划的思想非常相似。时间复杂度和动态规划一样0(m*n^2)
方法三:动态规划
记忆搜索方法和动态规划方法的联系:
1.记忆化搜索方法就是某种形态的动态规划方法;
2.记忆化搜索方法不关心到达某一个递归过程的路径,只是单纯地对计算过的递归过程进行记录,避免重复计算;
3.动态规划的方法则是规定好每一个递归过程的计算顺序,依次进行计算,后面的计算过程严格依赖前面的计算过程。
4.两者都是空间换时间的方法,也都有枚举的过程没区别就在于动态规划规定了计算顺序,而记忆搜索不用规定。
什么是动态规划方法?
1.其本质是利用申请的空间来记录每一个暴力搜索的计算结果,下次要用结果的时候直接使用,而不再进行重复的递归过程。
2.动态规划规定每一种递归状态的计算顺序,依次进行计算。
经过化简后的动规划方法的时间复杂度为O(m*n).
总结:虽然动态规划方法和记忆搜索方法本质上是相同的,但是由于动态规划规定了计算过程,所以使状态继续优化得以实现。
面试中遇到的暴力递归题目可以优化为动态规划方法的过程: