3 大解题套路，搞定动规面试

我是卢誉声，Autodesk 核心数据平台和计算平台资深工程师。

众所周知，在大厂面试和职场晋升中，动态规划一直是个大热门。

首先，动态规划考察了面试者的数学模型抽象能力和逻辑思维能力，可以反应个人在算法上的综合能力；其次，懂得了动态规划，能在工作中无限降低算法复杂度，在程序员晋升上也能胜人一筹。

但即使知道它很重要，很多人一想起来依然是“脑壳痛”，在工作和面试中也很难实践应用，问题出在哪了？

很简单：不理解动规的思想，无法掌握解题套路。

作为一种高级技术思想，动规是从一系列算法中演进而来的。求解动态规划的核心问题其实就是穷举，但穷举和动态规划在真正用的时候还是有区别的，首先要解决的是，什么样的问题要用动态规划？

一般让你求最大子数组、求最长递增子数组、求最长递增子序列或求最长公共子串、子序列等，这类都包含一个“最”字的问题，你就该警惕它是否是动归问题。

具体怎么判断呢？你可以按照这样的思考顺序来解决问题：

1. 优先考虑使用贪心算法的可能性；

2. 然后是暴力递归进行穷举（但这里的数据规模不大）；

3. 还是不行呢？选择动态规划！

那么，当我们遇到一个算法问题，到底是否该使用动态规划来求解呢？我列举了 5 大特点：

求最优解问题（最大值和最小值）

求可行性（True 或 False）

求方案总数

数据结构不可排序（Unsortable）

算法不可使用交换（Non-swappable）

如果面试题目出现这些特征，那么在 90% 的情况下你都能断言它就是一个动归问题。

那么动态规划该怎么学？如何有效的刷题，有什么可落地的解题套路？

动态规划题目类型多，难度高，没有固定模板，网上资料也往往比较凌乱，重在理论，不在解题。很多刷题资料，也不能带你很好地进行分类以及经验总结，很难有一个系统的方法带你从入门到精通。

在积累了大量的实战后，我梳理了一套「动态规划知识结构图」：

因此这次我与极客时间合作，推出了《动态规划面试宝典》专栏，为你提供一个较为全面的动态规划知识库，并带给你 3 大拿来即用的动规解题套路和实用高效的动归刷题指南，帮助你从容地应对面试。

专栏目录抢先看：

9 月 14 日 17:00，我在极客时间等你！

另外，极客时间还专门建立了交流群，进群可享受《动态规划面试宝典》上新内购优惠，扫码立即加入。