送你解题套路、刷题指南,再也不怕面试遇到动规!
又是一年金九银十,你跳槽了么?面试被虐了么?
想必面过大厂的人都知道,动态规划一直是个大热门。
首先,动态规划考察了面试者的数学模型抽象能力和逻辑思维能力,可以反应个人在算法上的综合能力;其次,懂得了动态规划,能在工作中无限降低算法复杂度,在程序员晋升上也能胜人一筹。
但即使知道它很重要,很多人一想起来依然是“脑壳痛”,在工作和面试中也很难实践应用,问题出在哪了?
很简单:不理解动规的思想,无法掌握解题套路。
作为一种高级技术思想,动规是从一系列算法中演进而来的。求解动态规划的核心问题其实就是穷举,但穷举和动态规划在真正用的时候还是有区别的,首先要解决的是,什么样的问题要用动态规划,怎么用?
举个例子,在实际工作中,除非你碰到的问题是简单到找出一个数组中最大的值这样,对这种问题来说,你可以对数组进行排序,然后取数组头或尾部的元素,如果觉得麻烦,你也可以直接遍历得到最值。不然的话,你就得考虑使用动态规划来解决这个问题了。这样的问题一般都会让你求最大子数组、求最长递增子数组、求最长递增子序列或求最长公共子串、子序列等等。不知道你发现没有,这些问题里都包含一个“最”字,如果出现了这个字,你就该警惕它是否是动归问题。
具体怎么判断呢?你可以按照这样的思考顺序来解决问题:
优先考虑使用贪心算法的可能性;
然后是暴力递归进行穷举(但这里的数据规模不大);
还是不行呢?选择动态规划!
那么,当我们遇到一个算法问题,到底是否该使用动态规划来求解呢?可以参考这
5 大特点:
求最优解问题(最大值和最小值)
求可行性(True 或 False)
求方案总数
数据结构不可排序(Unsortable)
算法不可使用交换(Non-swappable)
如果面试题目出现这些特征,那么在 90% 的情况下你都能断言它就是一个动归问题。
这套判断动规问题的思路,来自于卢誉声,Autodesk 核心数据平台和计算平台资深工程师,除此之外,我还找到了他整理的「动态规划知识结构图」,可以收藏?
其实,动态规划学习的难点在于题目类型多,难度高,没有固定模板,网上的资料也大多重在理论,不在解题,如何有效地刷题,找到可落地的解题套路才是重点。
而这些内容,在卢誉声的极客时间专栏《动态规划面试宝典》中都有涉及,刚刚上线,我已经读了部分章节,内容兼顾理论基础和有效的经验总结,可以为你提供一个较为全面的动态规划知识库,并带给你3 大拿来即用的动规解题套路和实用高效的动归刷题指南,能帮你更快地掌握动态规划问题,从容地应对面试。
这个专栏是如何设计的?
模块二,动态规划的套路。讲解动态规划问题的解题框架和套路。在此基础上,还会讲解面试真题,有针对性地套用解题框架。
模块三,举一反三,突破套路。针对几种特别易考的动态规划面试题进行总结,帮助你攻破套路。并在这些高级话题的基础上,提出设计动态规划算法的关键问题。另外,还有刷题指南,所谓孰能生巧,必要的练习还是要的。
扫码关注公众号,订阅更多精彩内容。