动态规划方法论

⚡ 30 秒速记

• 学 DP 别从概念入手，先做一道具体题，做完再回头对名词
• DP 说白了是「把算过的子问题记下来，别再算一遍」
• 三件套：状态是什么、怎么从小状态推到大状态、起点（边界）是什么
• 刷完题一定要复盘：这道题的状态为什么这么定义
• 题目是教具，换个说法还能写出来才算会

动态规划说白了就是：大问题能拆成小问题，小问题会被反复用到，那就算一次记下来。 刚开始学别急着啃「最优子结构」「状态转移方程」这些词，从抽象到抽象很难懂。我建议先拿爬楼梯这种题手推一遍，自己体会「到第 n 阶的走法只和前两阶有关」，再回头看这些名词就知道它们在说什么。做完题别急着走，花两分钟想清楚状态为什么这么定义，换一道题才迁移得过去。

动态规划是算法面试中的一个“大IP”，同时也是很多同学的心头痛。本节致力于用舒服的姿势帮助大家克服这块心病，因此开篇不能急于怼知识点，要先讲讲方法。

在笔者看来，对于动态规划的学习，最重要的是找到一个正确的学习切入点：如果你是一个对相关理论一无所知的初学者，自然不能急于一上来就生吞“模型”、“状态转移方程”等高端概念——大家谨记，动态规划是一种思想，所谓思想，就是非常好用，好用到爆的套路。我们学习一种思想，重要的是建立起对它的感性认知，而不是反复咀嚼那些对现在的你来说还非常生硬的文字概念——从抽象去理解抽象是意淫，从具体去理解抽象才是学习。

首先带大家一起解决一个实际的问题，然后逐步复盘问题的解决方案，最后从解决方案中提取出动态规划相关的概念、模型和技巧，实现对号入座。

从前面一系列章节的学习反馈中，笔者观察到一部分同学的阅读习惯非常“薄情”——打开小册只为做题，做完就溜，讲解部分基本是不看的。

这里想要提醒大家的是，题目本身不仅仅是命题点，更是素材、是教具，大家最终要关注到的还是题目背后的思想和方法。因此希望同学们能多给自己一点时间、多一些耐心去反刍和吸收知识。

💬 面试官追问

• 一句话解释动态规划，你会怎么说？

  记住已经算过的小问题答案，用它们拼出大问题的答案。比如斐波那契，f(5) 要 f(4) 和 f(3)，f(4) 又要 f(3)，f(3) 算一次存起来就行。

• 能背出「最优子结构、重叠子问题」，但换道题就不会定义状态，问题出在哪？

  只记了名词，没练过「从题目里抽状态」。拿一道新题，先问自己：最后一步是什么？最后一步之前的局面要用哪些量才能描述？这个量就是状态。

• 动态规划和贪心的区别？

  贪心每一步只挑当前最好的，不回头；DP 会把所有可能的上一步都比一遍再取最优。硬币 [1, 3, 4] 凑 6，贪心拿 4+1+1 三枚，DP 能找到 3+3 两枚。

• 动态规划题刷到多少道才算入门？

  数量不是关键。爬楼梯、硬币、背包、最长上升子序列、编辑距离这几类，每类能独立写出状态和转移，就够应付大部分前端面试了。

从“爬楼梯”问题说起

⚡ 30 秒速记

• 状态：f(i) = 爬到第 i 阶的走法数
• 按最后一步分类：从 i-1 跨一步，或从 i-2 跨两步 → f(i) = f(i-1) + f(i-2)
• 两类走法不重复、不遗漏，所以能直接相加
• 边界 f(1) = 1、f(2) = 2；时间 O(n)，滚动两个变量空间 O(1)
• n 很大时结果会超出 Number.MAX_SAFE_INTEGER，题目一般要求取模，或者用 BigInt

到第 n 阶的走法数等于到第 n-1 阶和第 n-2 阶的走法数之和，因为最后一步只能是跨 1 阶或跨 2 阶。 这两类走法最后一步不同，肯定不重复，又覆盖了所有情况，所以可以直接加。别一上来就说「这就是斐波那契」，面试官要听的是这个分类论证，规则一改（比如能跨 3 阶）你才能马上改出转移。写代码只要两个变量滚动：let a = 1, b = 2，循环里 [a, b] = [b, a + b]。