尧图网站开发 
刷过一阵子力扣的人大概率会在热题100里遇到这样一个坎一维动态规划已经做得顺风顺水递推公式闭着眼能写结果一到二维就懵了。状态变量从一个变成两个dp表格得画出来才敢下手边界条件稍不留神就越界更别提什么滚动数组压缩空间了。说实话多维动态规划是力扣热题100里区分度最高的一块也是大厂面试中动态规划考点的核心覆盖区。你把这一个专题啃透等于把技术面里DP题的八成套路都握在手里。这篇文章我打算把热题100里所有和多维DP相关的题目拉出来从状态定义、转移方程到初始化顺序逐题拆一遍再讲清楚哪些题跟它长得像但其实不是DP比如腐烂的橘子最后给出一份可以直接照着刷的题单和面试表达模板。适合正在刷热题100的人也适合那种一维DP会、二维DP一碰就废的选手。1. 多维动态规划的本质状态从一维变成二维到底难在哪想搞清楚为什么二维DP让那么多人卡壳得先想明白一维DP你是怎么学会的。一维DP的状态是一维数组下标通常代表“位置”“长度”或“数值”比如爬楼梯的dp[i]表示爬到第i阶的方法数打家劫舍的dp[i]表示偷到前i间房能拿到的最大值。下标的意思清清楚楚转移方程往往是“从上一步或前两步推过来”你画一条线就能理解。多维DP的复杂度提升不在于数学推导变难了而在于要同时跟踪两个维度的信息。以热题100里的经典题62. 不同路径为例机器人要从左上角走到右下角每次只能向右或向下走。问你一共有多少条不同的路径。这题状态必须定义为dp[i][j]表示“走到坐标(i, j)这个格子的路径条数”因为路径条数同时取决于横坐标和纵坐标只用一个下标根本表达不了两个位置维度的组合关系。从技术角度讲你相当于在一个二维坐标系上做动态规划。转移方程长这样dp[i][j] dp[i-1][j] dp[i][j-1]。它的含义是能走到(i,j)这个格子的路径要么来自上方格子(i-1,j)要么来自左方格子(i,j-1)两种来源的路径数相加就是总数。这个公式看起来简单但很多人第一次写还是会错原因通常是没搞清楚dp[i-1][j]和dp[i][j-1]究竟哪个代表“上”哪个代表“左”。初始化同样是重灾区。不同路径这道题第一行和第一列的格子只有一种走法因为只能沿着边缘走所以dp[0][j] 1dp[i][0] 1。你要是初始化成0整个转移就从源头开始错起。这个我后面会专门展开讲因为初始化错不是个例而是多维DP新手最常见的共性错误。1.1 状态定义所有转移方程的起点也是大多数人的拦路虎多维DP的状态定义有个非常实用的套路把题目的求解目标翻译成“dp[前i个][前j个] 某种属性值”。比如最长公共子序列dp[i][j]表示text1前i个字符和text2前j个字符的最长公共子序列长度编辑距离dp[i][j]表示word1前i个字符转换成word2前j个字符所需的最小操作数最小路径和dp[i][j]表示从左上角到(i,j)的最小路径和。你做多了会发现多维DP的状态定义就两种大方向一种是跟“位置”相关的状态里存坐标一种是跟“前缀”相关的状态里存长度。位置型的题目通常是路径类问题前缀型的题目通常是字符串匹配和编辑类问题。拿到题先判断归哪一类状态定义就能少走很多弯路。判断状态定义是否正确我个人的标准是三个问题这个状态能不能覆盖题目的所有信息能不能由前面的状态推出来最终答案放在哪个下标里三个问题都答上了状态定义基本就对了。答不上来说明你还没把状态空间想清楚不要急着写代码。1.2 转移方程不是靠背模板是画出来的很多教程教你“动态规划就是找递推关系”这话没错但对新手来说等于没说。我的经验是不画表根本推导不出多维DP的转移方程。二维DP的表格是天然的可视化工具把dp数组在纸上画成矩阵填几个小规模的格子转移关系直接就能看出来。以64. 最小路径和为例题目给一个m×n的网格每个格子有一个非负整数要找从左上角到右下角路径上的数字总和最小。状态定义是dp[i][j]表示到达(i,j)时的最小路径和。从左上角出发只能向右或向下走那么到达(i,j)的上一步只能来自左边或上边于是dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])。为什么会是取最小值而不是相加因为不同路径求的是“方案总数”而最小路径和求的是“路径代价的最优值”。同样是坐标型DP一个问题用加法一个用min差别来自题目问的内容不同。形式看起来像但分析逻辑完全不同。这正好说明转移方程不是从公式库里挑一个背而是得回到题目本身去想这个格子到底从哪些前驱状态来来了之后怎么合并。1.3 初始化与遍历顺序这两个细节决定了你能不能一次通过我见过太多人状态定义对了、转移方程也写对了提交还是错。十有八九是初始化或者遍历顺序出了问题。先说明初始化不同路径的第一行第一列全是1因为只有一种走法最小路径和的第一行只能从左往右累加第一列只能从上往下累加因为中间没有别的路径可选编辑距离的dp[i][0] idp[0][j] j因为把一个字符串变成空串只能逐个删除。遍历顺序的判断标准同样简单保证计算dp[i][j]时它所依赖的状态已经被计算过了。坐标型DP通常是双重循环从上到下、从左到右扫因为dp[i][j]依赖dp[i-1][j]和dp[i][j-1]都在当前格子的左方或上方按从左到右、从上到下的顺序计算它们自然是已经算好的。如果方向反过来那dp[i][j]依赖的状态还是初始值结果必然错误。有些题目的遍历顺序更微妙比如最长公共子序列里dp[i][j]依赖dp[i-1][j-1]、dp[i-1][j]和dp[i][j-1]三个方向按常规顺序遍历就一切正常。但如果是区间DP或者背包问题遍历顺序可能就变成从后往前扫了。所以别死记“按顺序遍历”而是要刻进思维里每次填表之前先问自己一句我依赖的那些格子现在填了没有2. 热题100里多维DP题型全拆解每一类都要怎么打热题100中的多维动态规划题目细看下来是有清晰派系的。把它们归好类你就不需要一题一题地硬背而是按“类”来打。我个人倾向于分为四派坐标路径派、双序列字符串派、背包变体派以及一个看起来像多维DP但其实不是的“伪多维派”。每一派的核心状态定义方式不同刷题时用的套路口径也不同。这里先把题目按类别列个表后面再逐个详解核心题目的关键思路方便你按图索骥题型类别代表题目核心状态表示难度感受坐标路径62/63/64/120dp[i][j] 表示走到(i,j)的属性值入门友好建立信心的关键双序列字符串5/1143/72dp[i][j] 表示前i、前j字符的关系值状态定义清晰转移细节多背包变体416/494dp[i][j] 表示前i物品在容量j下的答案第二维是容量而非位置伪多维994腐烂的橘子无状态转移多源BFS概念辨析题防止思维僵化2.1 坐标路径派从不同路径到最小路径和一张表吃透坐标路径派的核心套路就是我现在要说的这个模板读题之后先确定状态是“到达(i,j)的某属性值”然后看题目要求的是方案总数、最小代价还是最大收益决定转移时用加法、min还是max。这类题在热题100里有4道代表性题目分别是62. 不同路径、63. 不同路径II、64. 最小路径和、120. 三角形最小路径和。其中62和63是姊妹题。62是纯路径数63在62的基础上增加了障碍物网格里某些格子不能走。障碍物的处理方式很直接如果grid[i][j]等于1那dp[i][j]直接置0表示没有路径能到这个点同时初始化第一行第一列的时候遇到障碍物之后的所有格子都要置0因为障碍挡住了整条路。这里有个细节我特意提一下初始化不能只跳过障碍那一个格子而是障碍及其之后的位置都不能设为1了。64和120是求和的变体。64的最小路径和前面已经分析过状态转移取min。120是三角形最小路径和虽然看起来是三角形而不是矩形但处理思路是一样的只是边界条件少一些。三角形的每个位置只能由上一行的同列或前一列到达所以转移方程是dp[i][j] triangle[i][j] min(dp[i-1][j-1], dp[i-1][j])需要注意最左边和最右边的边界处理。这四道题建议连着刷顺序是62、63、64、120。你会明显感觉到从易到难、从裸模型到增加约束条件的递进感。把这四道吃透坐标路径这个派系基本上就站稳了后面遇到机器人、网格、矩阵、棋盘这类包装内核都是同一套东西。2.2 双序列字符串派最长公共子序列与编辑距离是门面双序列字符串派是多维DP里花活最多、也是面试官最爱考的一类。它的标准形式是给你两个字符串或序列让你求它们之间的关系常见的问法有最长公共子序列长度、最小编辑距离、能否匹配等。热题100里的代表题目有这么几道5. 最长回文子串、1143. 最长公共子序列、72. 编辑距离、10. 正则表达式匹配。最长公共子序列的状态定义是dp[i][j]表示text1前i个字符与text2前j个字符的最长公共子序列长度。转移时看text1[i-1]和text2[j-1]是否相等相等则dp[i][j] dp[i-1][j-1] 1不相等则dp[i][j] max(dp[i-1][j], dp[i][j-1])。这个不相等时的转移逻辑本质上是“当前两个字符至少放弃一个”它体现的是一种子序列问题的通用合并技巧。编辑距离的前面我会专门用一整节来做全流程推导这里先按下不表。最长回文子串虽然也是二维DP但和上面的双序列题不一样它是区间DPdp[i][j]表示s从i到j这个子串是否为回文串存的是布尔值。转移方程是dp[i][j] (s[i] s[j]) dp[i1][j-1]而且遍历顺序是长度从小往大不是简单的i从0到n、j从0到n。这里最容易掉坑我放在后面的常见问题里细说。2.3 一个特别容易混淆的题腐烂的橘子为什么不是动态规划热词里专门有人搜“力扣腐烂的橘子是什么题型”我多说两句。腐烂的橘子这道题很多人一看到是二维网格就条件反射地往多维DP上想然后发现状态转移完全写不出来整个人就懵了。其实这道题根本不是动态规划它是多源广度优先搜索多源BFS归类上属于图论或者模拟类题目。为什么不是DP因为动态规划要求问题具有“重叠子问题”和“最优子结构”转移关系是单向确定的计算方向是从已知状态推向未知状态。而腐烂的橘子里腐烂过程从多个初始烂橘子同时向四周扩散每一分钟扩散一层这个扩散过程有明显的“时间步”概念天然适合BFS分层处理。你如果强行用DP去定义“某个橘子腐烂的最短时间”其实也不是完全不行但它本质是在图上求最短路BFS才是正解而且代码写起来也直观得多。我的建议是刷热题100的时候尽量做一次题型归类不要被“多维”两个字绑架。看到二维网格先别急想想题目是求路径条数还是求扩散层数是求最优值还是在图上遍历。想清楚这一步你后面的解题路径就不会跑偏也省去很多无用功。3. 一道题吃透多维DP完整推导编辑距离的入门到进阶前面分类讲了很多题型的套路现在我把这十几年的经验浓缩到一个经典案例上——力扣72. 编辑距离。这道题是热题100里多维DP的顶配也是大厂面试的动态规划高频题。我的建议是不要直接背答案跟着我一步步推你会逐步建立一种“多维DP也能手推出来”的自信。编辑距离的题目描述是给你两个单词word1和word2你可以对word1执行插入、删除、替换三种操作每次操作计1求把word1转换成word2所需的最少操作次数。这个“最少操作次数”就是编辑距离是自然语言处理里衡量字符串相似度的经典指标。3.1 状态定义与初始化为什么dp[i][j]存的是前i和前j不是下标i和j编辑距离的状态定义是dp[i][j] 将word1的前i个字符转换成word2的前j个字符所需的最小操作数。注意这里的i和j是“长度”不是“下标”这是很多人的第一道坎。比如word1 horseword2 ros那么dp[3][2]表示把hor前3个字符转换成ro前2个字符需要的最小操作数。初始化为什么是dp[i][0] i和dp[0][j] j因为把一个长度为i的字符串变成空字符串唯一的办法就是删除i个字符所以操作数是i反过来把空字符串变成长度为j的字符串只能逐个插入j个字符所以操作数是j。这一行一列的初始值是整个表格的地基后面所有格子都从它们推算出来。很多人会问为什么不用dp[i][j]表示word1第i个字符变化到word2第j个字符而非要用“前i个”。关键在于编辑操作的性质你永远是在处理“前缀”已经处理完的字符不影响后续操作。如果你用单字符下标表示状态就无法表达“已经消耗了多少字符”这个信息转移方程根本写不完整。前缀式定义把“已处理长度”显式地带进了状态才能正确覆盖所有操作组合。3.2 转移方程推导插入、删除、替换三个操作如何映射到grid状态定义好了之后转移方程是整个推导的核心。对word1前i个字符和word2前j个字符看它们的最后一个字符即word1[i-1]和word2[j-1]第一种情况两个字符相等。这时候不需要做任何操作dp[i][j]直接等于dp[i-1][j-1]因为我们只需要把word1的前i-1个字符转成word2的前j-1个字符就行。第二种情况两个字符不相等。这时有三种操作可能删除删除word1的第i个字符让word1的前i-1个字符去匹配word2的前j个字符。操作数是dp[i-1][j] 1。插入在word1的末尾插入一个word2[j-1]的字符这时候word1的前i个字符需要先匹配上word2的前j-1个字符再靠这个新插入的字符去匹配最后一位。操作数是dp[i][j-1] 1。替换把word1的第i个字符替换成word2的第j个字符然后前i-1个字符去匹配前j-1个字符。操作数是dp[i-1][j-1] 1。三种操作里取最小值就是当前dp[i][j]的最优解对应代码def minDistance(word1: str, word2: str) - int: m, n len(word1), len(word2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j for i in range(1, m 1): for j in range(1, n 1): if word1[i - 1] word2[j - 1]: dp[i][j] dp[i - 1][j - 1] else: dp[i][j] min( dp[i - 1][j] 1, # 删除 dp[i][j - 1] 1, # 插入 dp[i - 1][j - 1] 1 # 替换 ) return dp[m][n]代码写出来就十几行但这里面每一步推导都别省。我见过太多人面试时当场背这道题的代码背得出来但被面试官问一句“为什么dp[i][j-1]1代表插入”就卡住了。如果你能把上面这一段推导讲清楚面试官对你这道题的评价绝对比背代码的人高一档。3.3 空间优化从二维表到一维数组滚动数组到底怎么滚动编辑距离完整填一张m×n的表格空间复杂度是O(mn)。题目如果只要求返回最终结果不要求回溯具体操作路径那我们可以用滚动数组把空间压到O(min(m,n))也就是只保留一维数组。这个优化思路不止适配编辑距离几乎所有坐标型和双序列型DP都能用所以掌握它的原理比记住代码重要。滚动数组的原理是观察转移方程dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1依赖的是上一行同列、当前行前一列和上一行前一列这三个值。如果只用一维数组dp[j]保存当前行那dp[j]更新之前存的是上一行同列的值dp[j-1]更新之后是当前行前一列的值缺的是上一行前一列的值。所以需要在更新dp[j]之前用临时变量把dp[j]的旧值存下来作为下一轮要用到的“左上角”值。对应的Python代码长这样def minDistance_optimized(word1: str, word2: str) - int: m, n len(word1), len(word2) if m n: word1, word2 word2, word1 m, n n, m dp list(range(n 1)) for i in range(1, m 1): prev dp[0] dp[0] i for j in range(1, n 1): temp dp[j] if word1[i - 1] word2[j - 1]: dp[j] prev else: dp[j] min(dp[j] 1, dp[j - 1] 1, prev 1) prev temp return dp[n]这里我先交换word1和word2让较短的字符串作为列方向这样dp数组长度更短空间利用最优。你在面试中可以主动提到这个优化因为这说明你不仅会写二维DP还理解DP表的存储结构与依赖关系这在面试评价里是一个相当大的加分项。4. 多维DP的刷题路线与时间安排从零到面试够用的实战路径光知道题型还不够很多人问过我“热题100到底应该按什么顺序刷多维DP这一块又应该什么时候开始碰”我根据自己的刷题经验给出一条相对平滑的路线。它不是唯一的答案但我确实是这么带自己走过来的你照这个顺序走能大大减少中途放弃的概率。先把大原则放在前面多维DP不是第一遍刷热题时就应该死磕的。你至少需要先过一遍简单难度的一维DP对“状态”“转移”“初始化”这三个词有体感了再开始多维DP。否则你连dp[i]都没整明白直接上dp[i][j]学到的只会是“背模板”而不是“设计状态”的能力。4.1 阶段一一维DP打底建立状态机思维约1周这个阶段的题不用多挑5到8道经典的就行爬楼梯、打家劫舍、最大子数组和、零钱兑换、最长递增子序列。这五道题覆盖了一维DP的几大基本形态斐波那契型、前驱决策型、区间扫型、背包型、子序列型。每道题做到什么程度算过关不看题解能独立写出完整代码并且能把状态定义、转移方程、初始化和复杂度这四件事用口头表达一遍。完成这个阶段后你对“动态规划是一张表从左往右填填完读答案”这件事就有了肌肉记忆。这时候进入多维DP你心里至少知道自己缺什么不是缺概念而是缺怎么把一张二维表跑起来的实操经验。4.2 阶段二坐标路径四连刷上手多维度填表约3到4天对应我前面讲的坐标路径派按62、63、64、120的顺序刷。这四道题目的状态定义和转移方程几乎可以套用同一个模板你会在大概第三题的时候开始产生“是不是所有网格题都这么解”的错觉这个错觉恰恰说明你已经掌握了这个类型的基本套路。刷的时候给自己定个规矩每道题提交通过之后用白板重新画一次dp表填一个4×4或5×5的小规模输入把表的整个填制过程走一遍。这一步听起来麻烦但对建立多维空间感和查错能力特别关键很多人跳过它到了编辑距离就彻底跟不上。4.3 阶段三双序列字符串题啃硬骨头约1周这个阶段题少但都难先刷1143最长公共子序列再刷72编辑距离接着是5最长回文子串最后有余力的再看10正则表达式匹配。1143和72的思路高度相似都是“前i与前j”的转移框架连起来刷相当于一道题复习两遍。5是区间DP转移方程虽然简单但遍历顺序容易出错我建议你故意写错一次遍历顺序看看输出错成什么样这样印象最深。这个阶段每天最多刷两道不要贪多。每道题都值得你花至少半小时推导再花十分钟写代码最后花十分钟复盘。如果遇到完全卡壳的题看题解不可耻但看完之后一定要自己独立重写一遍并且在你自己的题解笔记里用一句话总结这题的“关键洞察”。比如编辑距离的关键洞察是“操作映射到矩阵的三个方向”最长回文子串的关键洞察是“短子串先判断长子串依赖短子串”。4.4 阶段四面试冲刺从会做到会讲约3天多维DP刷到位之后你还需要一个“面试模式”的转换。面试和刷题最大的区别是面试官更关注你能不能把思路讲清楚。尤其在动态规划这种抽象题目上你如果一上来就写代码哪怕写对了面试官也容易怀疑你是背的。所以你需要在刷题阶段就有意识地练习口头输出。我给自己定的表达模板是四段式第一句说“这道题可以用动态规划解决因为存在重叠子问题和最优子结构”第二句说“我定义dp[i][j]表示某某意思”第三句说“转移方程是某某因为当前状态来自某某前驱状态”第四句说“初始化是某某最终答案是dp[m][n]时间复杂度O(mn)空间复杂度可以优化到O(n)”。四句话讲完面试官基本上已经知道你是真懂了。5. 多维DP的常见错误与调试技巧踩过的坑全在这里多维DP的代码量普遍不大但调试起来经常让人怀疑人生。因为逻辑藏在状态转移里你很难靠“打个日志看看”来定位错误。这一节我把我刷题以来踩过和见过的所有常见错误整理成一张速查表再附上我自己最常用的调试技巧希望帮你少走一些弯路。5.1 高频错误速查表初始化、遍历顺序、边界处理错误类型具体描述典型后果解决思路初始化错误第一行第一列没有正确设置整个dp表从源头错起先手算长度为1的边界情况遍历顺序错误依赖状态在计算时还未填充结果随机或部分正确打印dp表检查依赖格子是否已填下标偏移错误字符串第i个字符误写成word1[i]而非word1[i-1]越界或结果莫名偏大记住dp[i]对应前i个字符状态定义混淆用下标表示而非前缀长度转移方程逻辑混乱重新提炼状态定义套“前i个”模板边界条件遗漏空字符串、长度为1的串未单独验证特定用例下报错提交前先测最小输入空间优化后逻辑错滚动数组时左上角值未保存结果近乎随机用完整二维表校准一维版本初始化错误在多维DP里尤其隐蔽因为大样例可能跑出正确答案但小样例一测就崩。比如63不同路径II你能想到处理障碍物但可能忘记处理“第一行第一列本身是障碍”的情况。这类边界case是面试官和评测系统最喜欢藏雷的地方你刷题的时候可以在纸上列出一组小输入把所有边界情况都覆盖一遍再写代码。5.2 打印dp表的调试大法用可视化打破“想当然”我调试多维DP用得最多的方法不是debugger而是手动打印dp表。做法很简单在双重循环跑完之后把整个dp矩阵用格式化的方式打印到终端然后拿一个小规模的输入自己拿笔在纸上把期望的dp表填一遍两张表一对比错误立刻现形。比如编辑距离有一个经典小用例word1 abcword2 yabd。手算期望的dp表前三行三列是什么第一行应该依次是0、1、2、3、3因为空串变成空串是0变成y是插入1变成ya是插入2变成yab是插入3变成yabd是插入4不对word2 yabd长度为4所以第一行是0、1、2、3、4。第二行的第一个值是1表示a变成空串需要删1个字符。这些小数你手一算代码对不对一目了然。打印dp表还有一个额外好处你会慢慢建立起“填表直觉”。填多了之后你看到一个多维DP题脑子里会自动浮现出一张二维表的形状转移方程不再是一个抽象的公式而是表里某个格子从哪个方向取值的问题。这种感觉一旦建立起来多维DP对你来说就再也不是难题了。5.3 独家小技巧先写暴力递归再改成DP彻底告别“不会推转移方程”接下来这个是压箱底的技巧我觉得它比任何模板都值得记住。如果你拿到一个多维DP题完全不知道转移方程怎么写那就先别想DP这回事直接写暴力递归。用递归去枚举所有可能的选择不管重复计算不重复计算先把正确性保证住。然后观察递归函数的参数——那些参数基本就是要放进dp里的维度递归函数里的状态转移逻辑就是转移方程的原型。以编辑距离为例暴力递归写法是这样的定义一个dfs(i, j)表示把word1前i个字符转换成word2前j个字符的最小操作数然后递归地去计算三种操作对应的情况。你会发现这个dfs(i, j)的参数i和j正好对应用二维表的行和列dfs内部的递归分支正好对应二维表里依赖的若干个前驱格子递归的终止条件正好对应dp数组的初始化。把递归改成自底向上的循环填表一个标准的DP代码就出来了。这个“先递归后DP”的路径比直接看题解学DP模板要踏实得多。因为你看题解学的是别人消化过的结论而递归是你自己枚举出来的过程。两种方式都能AC但只有后者能让你在遇到新题时不慌。6. 把多维DP刷明白之后面试官到底在考察你什么最后我想聊一个很多人刷题时容易忽略的问题热题100里的多维DP题面试官到底在测你什么只看答案的话你可能会觉得就是在考你“会不会这个算法”但实际上面试官考的是几层东西的叠buff。第一层是建模能力。拿到一个现实问题你能不能抽象出状态变量、找到转移关系、确定边界条件。这是动态规划的本质也是绝大多数非算法岗位的日常工作中根本不会专门练的能力。刷多维DP题本质就是在反复训练这种从复杂场景里抽取结构化模型的能力。第二层是代码功力。多维DP的代码不算长但它对下标处理、边界处理、代码整洁度的要求很高。一个能一次AC编辑距离的人大概率写其他稍复杂的业务代码时也不会出现低级越界和脏数据问题。这解释了为什么大厂面试官喜欢用DP题来筛人因为它是少数能把“思维能力”和“代码能力”同时考察到的题型。第三层是沟通表达。面试当场写DP题你要一边写一边讲什么状态下定义、为什么要优化空间、复杂度是多少。这是一个非常真实的团队协作模拟因为实际工作中你就是需要一边写代码一边跟同事解释思路。很多人在白板上写代码时手在抖、嘴在瓢不是不会写而是表达训练不够。所以我前面特意建议你刷完题后自己当面试官讲一遍目的就是把沟通这一层也练起来。多维动态规划在热题100里的题量不算最多的但它的战略地位在我看来远超其他专题。你把这块啃下来动态规划这个考点基本就拿捏了后面再遇到什么“打家劫舍III”“买卖股票的最佳时机”之类的一维DP变体反而会有一种下山打小怪的松弛感。我个人刷题的时候有个体会多维DP适合放在一天精力最充沛的时候刷千万不要在熬夜状态下碰因为它的调试过程对脑力要求真的高。每次卡题超过40分钟就果断看题解然后第二天再独立默写一遍。这种“先看后默”的节奏虽然慢但留得下来的内化率特别高。你可以试试看一周之后再来做热题100里的多维DP那种手到擒来的感觉会让前面所有的死磕都变得很值。 
刷过一阵子力扣的人大概率会在热题100里遇到这样一个坎一维动态规划已经做得顺风顺水递推公式闭着眼能写结果一到二维就懵了。状态变量从一个变成两个dp表格得画出来才敢下手边界条件稍不留神就越界更别提什么滚动数组压缩空间了。说实话多维动态规划是力扣热题100里区分度最高的一块也是大厂面试中动态规划考点的核心覆盖区。你把这一个专题啃透等于把技术面里DP题的八成套路都握在手里。这篇文章我打算把热题100里所有和多维DP相关的题目拉出来从状态定义、转移方程到初始化顺序逐题拆一遍再讲清楚哪些题跟它长得像但其实不是DP比如腐烂的橘子最后给出一份可以直接照着刷的题单和面试表达模板。适合正在刷热题100的人也适合那种一维DP会、二维DP一碰就废的选手。1. 多维动态规划的本质状态从一维变成二维到底难在哪想搞清楚为什么二维DP让那么多人卡壳得先想明白一维DP你是怎么学会的。一维DP的状态是一维数组下标通常代表“位置”“长度”或“数值”比如爬楼梯的dp[i]表示爬到第i阶的方法数打家劫舍的dp[i]表示偷到前i间房能拿到的最大值。下标的意思清清楚楚转移方程往往是“从上一步或前两步推过来”你画一条线就能理解。多维DP的复杂度提升不在于数学推导变难了而在于要同时跟踪两个维度的信息。以热题100里的经典题62. 不同路径为例机器人要从左上角走到右下角每次只能向右或向下走。问你一共有多少条不同的路径。这题状态必须定义为dp[i][j]表示“走到坐标(i, j)这个格子的路径条数”因为路径条数同时取决于横坐标和纵坐标只用一个下标根本表达不了两个位置维度的组合关系。从技术角度讲你相当于在一个二维坐标系上做动态规划。转移方程长这样dp[i][j] dp[i-1][j] dp[i][j-1]。它的含义是能走到(i,j)这个格子的路径要么来自上方格子(i-1,j)要么来自左方格子(i,j-1)两种来源的路径数相加就是总数。这个公式看起来简单但很多人第一次写还是会错原因通常是没搞清楚dp[i-1][j]和dp[i][j-1]究竟哪个代表“上”哪个代表“左”。初始化同样是重灾区。不同路径这道题第一行和第一列的格子只有一种走法因为只能沿着边缘走所以dp[0][j] 1dp[i][0] 1。你要是初始化成0整个转移就从源头开始错起。这个我后面会专门展开讲因为初始化错不是个例而是多维DP新手最常见的共性错误。1.1 状态定义所有转移方程的起点也是大多数人的拦路虎多维DP的状态定义有个非常实用的套路把题目的求解目标翻译成“dp[前i个][前j个] 某种属性值”。比如最长公共子序列dp[i][j]表示text1前i个字符和text2前j个字符的最长公共子序列长度编辑距离dp[i][j]表示word1前i个字符转换成word2前j个字符所需的最小操作数最小路径和dp[i][j]表示从左上角到(i,j)的最小路径和。你做多了会发现多维DP的状态定义就两种大方向一种是跟“位置”相关的状态里存坐标一种是跟“前缀”相关的状态里存长度。位置型的题目通常是路径类问题前缀型的题目通常是字符串匹配和编辑类问题。拿到题先判断归哪一类状态定义就能少走很多弯路。判断状态定义是否正确我个人的标准是三个问题这个状态能不能覆盖题目的所有信息能不能由前面的状态推出来最终答案放在哪个下标里三个问题都答上了状态定义基本就对了。答不上来说明你还没把状态空间想清楚不要急着写代码。1.2 转移方程不是靠背模板是画出来的很多教程教你“动态规划就是找递推关系”这话没错但对新手来说等于没说。我的经验是不画表根本推导不出多维DP的转移方程。二维DP的表格是天然的可视化工具把dp数组在纸上画成矩阵填几个小规模的格子转移关系直接就能看出来。以64. 最小路径和为例题目给一个m×n的网格每个格子有一个非负整数要找从左上角到右下角路径上的数字总和最小。状态定义是dp[i][j]表示到达(i,j)时的最小路径和。从左上角出发只能向右或向下走那么到达(i,j)的上一步只能来自左边或上边于是dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])。为什么会是取最小值而不是相加因为不同路径求的是“方案总数”而最小路径和求的是“路径代价的最优值”。同样是坐标型DP一个问题用加法一个用min差别来自题目问的内容不同。形式看起来像但分析逻辑完全不同。这正好说明转移方程不是从公式库里挑一个背而是得回到题目本身去想这个格子到底从哪些前驱状态来来了之后怎么合并。1.3 初始化与遍历顺序这两个细节决定了你能不能一次通过我见过太多人状态定义对了、转移方程也写对了提交还是错。十有八九是初始化或者遍历顺序出了问题。先说明初始化不同路径的第一行第一列全是1因为只有一种走法最小路径和的第一行只能从左往右累加第一列只能从上往下累加因为中间没有别的路径可选编辑距离的dp[i][0] idp[0][j] j因为把一个字符串变成空串只能逐个删除。遍历顺序的判断标准同样简单保证计算dp[i][j]时它所依赖的状态已经被计算过了。坐标型DP通常是双重循环从上到下、从左到右扫因为dp[i][j]依赖dp[i-1][j]和dp[i][j-1]都在当前格子的左方或上方按从左到右、从上到下的顺序计算它们自然是已经算好的。如果方向反过来那dp[i][j]依赖的状态还是初始值结果必然错误。有些题目的遍历顺序更微妙比如最长公共子序列里dp[i][j]依赖dp[i-1][j-1]、dp[i-1][j]和dp[i][j-1]三个方向按常规顺序遍历就一切正常。但如果是区间DP或者背包问题遍历顺序可能就变成从后往前扫了。所以别死记“按顺序遍历”而是要刻进思维里每次填表之前先问自己一句我依赖的那些格子现在填了没有2. 热题100里多维DP题型全拆解每一类都要怎么打热题100中的多维动态规划题目细看下来是有清晰派系的。把它们归好类你就不需要一题一题地硬背而是按“类”来打。我个人倾向于分为四派坐标路径派、双序列字符串派、背包变体派以及一个看起来像多维DP但其实不是的“伪多维派”。每一派的核心状态定义方式不同刷题时用的套路口径也不同。这里先把题目按类别列个表后面再逐个详解核心题目的关键思路方便你按图索骥题型类别代表题目核心状态表示难度感受坐标路径62/63/64/120dp[i][j] 表示走到(i,j)的属性值入门友好建立信心的关键双序列字符串5/1143/72dp[i][j] 表示前i、前j字符的关系值状态定义清晰转移细节多背包变体416/494dp[i][j] 表示前i物品在容量j下的答案第二维是容量而非位置伪多维994腐烂的橘子无状态转移多源BFS概念辨析题防止思维僵化2.1 坐标路径派从不同路径到最小路径和一张表吃透坐标路径派的核心套路就是我现在要说的这个模板读题之后先确定状态是“到达(i,j)的某属性值”然后看题目要求的是方案总数、最小代价还是最大收益决定转移时用加法、min还是max。这类题在热题100里有4道代表性题目分别是62. 不同路径、63. 不同路径II、64. 最小路径和、120. 三角形最小路径和。其中62和63是姊妹题。62是纯路径数63在62的基础上增加了障碍物网格里某些格子不能走。障碍物的处理方式很直接如果grid[i][j]等于1那dp[i][j]直接置0表示没有路径能到这个点同时初始化第一行第一列的时候遇到障碍物之后的所有格子都要置0因为障碍挡住了整条路。这里有个细节我特意提一下初始化不能只跳过障碍那一个格子而是障碍及其之后的位置都不能设为1了。64和120是求和的变体。64的最小路径和前面已经分析过状态转移取min。120是三角形最小路径和虽然看起来是三角形而不是矩形但处理思路是一样的只是边界条件少一些。三角形的每个位置只能由上一行的同列或前一列到达所以转移方程是dp[i][j] triangle[i][j] min(dp[i-1][j-1], dp[i-1][j])需要注意最左边和最右边的边界处理。这四道题建议连着刷顺序是62、63、64、120。你会明显感觉到从易到难、从裸模型到增加约束条件的递进感。把这四道吃透坐标路径这个派系基本上就站稳了后面遇到机器人、网格、矩阵、棋盘这类包装内核都是同一套东西。2.2 双序列字符串派最长公共子序列与编辑距离是门面双序列字符串派是多维DP里花活最多、也是面试官最爱考的一类。它的标准形式是给你两个字符串或序列让你求它们之间的关系常见的问法有最长公共子序列长度、最小编辑距离、能否匹配等。热题100里的代表题目有这么几道5. 最长回文子串、1143. 最长公共子序列、72. 编辑距离、10. 正则表达式匹配。最长公共子序列的状态定义是dp[i][j]表示text1前i个字符与text2前j个字符的最长公共子序列长度。转移时看text1[i-1]和text2[j-1]是否相等相等则dp[i][j] dp[i-1][j-1] 1不相等则dp[i][j] max(dp[i-1][j], dp[i][j-1])。这个不相等时的转移逻辑本质上是“当前两个字符至少放弃一个”它体现的是一种子序列问题的通用合并技巧。编辑距离的前面我会专门用一整节来做全流程推导这里先按下不表。最长回文子串虽然也是二维DP但和上面的双序列题不一样它是区间DPdp[i][j]表示s从i到j这个子串是否为回文串存的是布尔值。转移方程是dp[i][j] (s[i] s[j]) dp[i1][j-1]而且遍历顺序是长度从小往大不是简单的i从0到n、j从0到n。这里最容易掉坑我放在后面的常见问题里细说。2.3 一个特别容易混淆的题腐烂的橘子为什么不是动态规划热词里专门有人搜“力扣腐烂的橘子是什么题型”我多说两句。腐烂的橘子这道题很多人一看到是二维网格就条件反射地往多维DP上想然后发现状态转移完全写不出来整个人就懵了。其实这道题根本不是动态规划它是多源广度优先搜索多源BFS归类上属于图论或者模拟类题目。为什么不是DP因为动态规划要求问题具有“重叠子问题”和“最优子结构”转移关系是单向确定的计算方向是从已知状态推向未知状态。而腐烂的橘子里腐烂过程从多个初始烂橘子同时向四周扩散每一分钟扩散一层这个扩散过程有明显的“时间步”概念天然适合BFS分层处理。你如果强行用DP去定义“某个橘子腐烂的最短时间”其实也不是完全不行但它本质是在图上求最短路BFS才是正解而且代码写起来也直观得多。我的建议是刷热题100的时候尽量做一次题型归类不要被“多维”两个字绑架。看到二维网格先别急想想题目是求路径条数还是求扩散层数是求最优值还是在图上遍历。想清楚这一步你后面的解题路径就不会跑偏也省去很多无用功。3. 一道题吃透多维DP完整推导编辑距离的入门到进阶前面分类讲了很多题型的套路现在我把这十几年的经验浓缩到一个经典案例上——力扣72. 编辑距离。这道题是热题100里多维DP的顶配也是大厂面试的动态规划高频题。我的建议是不要直接背答案跟着我一步步推你会逐步建立一种“多维DP也能手推出来”的自信。编辑距离的题目描述是给你两个单词word1和word2你可以对word1执行插入、删除、替换三种操作每次操作计1求把word1转换成word2所需的最少操作次数。这个“最少操作次数”就是编辑距离是自然语言处理里衡量字符串相似度的经典指标。3.1 状态定义与初始化为什么dp[i][j]存的是前i和前j不是下标i和j编辑距离的状态定义是dp[i][j] 将word1的前i个字符转换成word2的前j个字符所需的最小操作数。注意这里的i和j是“长度”不是“下标”这是很多人的第一道坎。比如word1 horseword2 ros那么dp[3][2]表示把hor前3个字符转换成ro前2个字符需要的最小操作数。初始化为什么是dp[i][0] i和dp[0][j] j因为把一个长度为i的字符串变成空字符串唯一的办法就是删除i个字符所以操作数是i反过来把空字符串变成长度为j的字符串只能逐个插入j个字符所以操作数是j。这一行一列的初始值是整个表格的地基后面所有格子都从它们推算出来。很多人会问为什么不用dp[i][j]表示word1第i个字符变化到word2第j个字符而非要用“前i个”。关键在于编辑操作的性质你永远是在处理“前缀”已经处理完的字符不影响后续操作。如果你用单字符下标表示状态就无法表达“已经消耗了多少字符”这个信息转移方程根本写不完整。前缀式定义把“已处理长度”显式地带进了状态才能正确覆盖所有操作组合。3.2 转移方程推导插入、删除、替换三个操作如何映射到grid状态定义好了之后转移方程是整个推导的核心。对word1前i个字符和word2前j个字符看它们的最后一个字符即word1[i-1]和word2[j-1]第一种情况两个字符相等。这时候不需要做任何操作dp[i][j]直接等于dp[i-1][j-1]因为我们只需要把word1的前i-1个字符转成word2的前j-1个字符就行。第二种情况两个字符不相等。这时有三种操作可能删除删除word1的第i个字符让word1的前i-1个字符去匹配word2的前j个字符。操作数是dp[i-1][j] 1。插入在word1的末尾插入一个word2[j-1]的字符这时候word1的前i个字符需要先匹配上word2的前j-1个字符再靠这个新插入的字符去匹配最后一位。操作数是dp[i][j-1] 1。替换把word1的第i个字符替换成word2的第j个字符然后前i-1个字符去匹配前j-1个字符。操作数是dp[i-1][j-1] 1。三种操作里取最小值就是当前dp[i][j]的最优解对应代码def minDistance(word1: str, word2: str) - int: m, n len(word1), len(word2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j for i in range(1, m 1): for j in range(1, n 1): if word1[i - 1] word2[j - 1]: dp[i][j] dp[i - 1][j - 1] else: dp[i][j] min( dp[i - 1][j] 1, # 删除 dp[i][j - 1] 1, # 插入 dp[i - 1][j - 1] 1 # 替换 ) return dp[m][n]代码写出来就十几行但这里面每一步推导都别省。我见过太多人面试时当场背这道题的代码背得出来但被面试官问一句“为什么dp[i][j-1]1代表插入”就卡住了。如果你能把上面这一段推导讲清楚面试官对你这道题的评价绝对比背代码的人高一档。3.3 空间优化从二维表到一维数组滚动数组到底怎么滚动编辑距离完整填一张m×n的表格空间复杂度是O(mn)。题目如果只要求返回最终结果不要求回溯具体操作路径那我们可以用滚动数组把空间压到O(min(m,n))也就是只保留一维数组。这个优化思路不止适配编辑距离几乎所有坐标型和双序列型DP都能用所以掌握它的原理比记住代码重要。滚动数组的原理是观察转移方程dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1依赖的是上一行同列、当前行前一列和上一行前一列这三个值。如果只用一维数组dp[j]保存当前行那dp[j]更新之前存的是上一行同列的值dp[j-1]更新之后是当前行前一列的值缺的是上一行前一列的值。所以需要在更新dp[j]之前用临时变量把dp[j]的旧值存下来作为下一轮要用到的“左上角”值。对应的Python代码长这样def minDistance_optimized(word1: str, word2: str) - int: m, n len(word1), len(word2) if m n: word1, word2 word2, word1 m, n n, m dp list(range(n 1)) for i in range(1, m 1): prev dp[0] dp[0] i for j in range(1, n 1): temp dp[j] if word1[i - 1] word2[j - 1]: dp[j] prev else: dp[j] min(dp[j] 1, dp[j - 1] 1, prev 1) prev temp return dp[n]这里我先交换word1和word2让较短的字符串作为列方向这样dp数组长度更短空间利用最优。你在面试中可以主动提到这个优化因为这说明你不仅会写二维DP还理解DP表的存储结构与依赖关系这在面试评价里是一个相当大的加分项。4. 多维DP的刷题路线与时间安排从零到面试够用的实战路径光知道题型还不够很多人问过我“热题100到底应该按什么顺序刷多维DP这一块又应该什么时候开始碰”我根据自己的刷题经验给出一条相对平滑的路线。它不是唯一的答案但我确实是这么带自己走过来的你照这个顺序走能大大减少中途放弃的概率。先把大原则放在前面多维DP不是第一遍刷热题时就应该死磕的。你至少需要先过一遍简单难度的一维DP对“状态”“转移”“初始化”这三个词有体感了再开始多维DP。否则你连dp[i]都没整明白直接上dp[i][j]学到的只会是“背模板”而不是“设计状态”的能力。4.1 阶段一一维DP打底建立状态机思维约1周这个阶段的题不用多挑5到8道经典的就行爬楼梯、打家劫舍、最大子数组和、零钱兑换、最长递增子序列。这五道题覆盖了一维DP的几大基本形态斐波那契型、前驱决策型、区间扫型、背包型、子序列型。每道题做到什么程度算过关不看题解能独立写出完整代码并且能把状态定义、转移方程、初始化和复杂度这四件事用口头表达一遍。完成这个阶段后你对“动态规划是一张表从左往右填填完读答案”这件事就有了肌肉记忆。这时候进入多维DP你心里至少知道自己缺什么不是缺概念而是缺怎么把一张二维表跑起来的实操经验。4.2 阶段二坐标路径四连刷上手多维度填表约3到4天对应我前面讲的坐标路径派按62、63、64、120的顺序刷。这四道题目的状态定义和转移方程几乎可以套用同一个模板你会在大概第三题的时候开始产生“是不是所有网格题都这么解”的错觉这个错觉恰恰说明你已经掌握了这个类型的基本套路。刷的时候给自己定个规矩每道题提交通过之后用白板重新画一次dp表填一个4×4或5×5的小规模输入把表的整个填制过程走一遍。这一步听起来麻烦但对建立多维空间感和查错能力特别关键很多人跳过它到了编辑距离就彻底跟不上。4.3 阶段三双序列字符串题啃硬骨头约1周这个阶段题少但都难先刷1143最长公共子序列再刷72编辑距离接着是5最长回文子串最后有余力的再看10正则表达式匹配。1143和72的思路高度相似都是“前i与前j”的转移框架连起来刷相当于一道题复习两遍。5是区间DP转移方程虽然简单但遍历顺序容易出错我建议你故意写错一次遍历顺序看看输出错成什么样这样印象最深。这个阶段每天最多刷两道不要贪多。每道题都值得你花至少半小时推导再花十分钟写代码最后花十分钟复盘。如果遇到完全卡壳的题看题解不可耻但看完之后一定要自己独立重写一遍并且在你自己的题解笔记里用一句话总结这题的“关键洞察”。比如编辑距离的关键洞察是“操作映射到矩阵的三个方向”最长回文子串的关键洞察是“短子串先判断长子串依赖短子串”。4.4 阶段四面试冲刺从会做到会讲约3天多维DP刷到位之后你还需要一个“面试模式”的转换。面试和刷题最大的区别是面试官更关注你能不能把思路讲清楚。尤其在动态规划这种抽象题目上你如果一上来就写代码哪怕写对了面试官也容易怀疑你是背的。所以你需要在刷题阶段就有意识地练习口头输出。我给自己定的表达模板是四段式第一句说“这道题可以用动态规划解决因为存在重叠子问题和最优子结构”第二句说“我定义dp[i][j]表示某某意思”第三句说“转移方程是某某因为当前状态来自某某前驱状态”第四句说“初始化是某某最终答案是dp[m][n]时间复杂度O(mn)空间复杂度可以优化到O(n)”。四句话讲完面试官基本上已经知道你是真懂了。5. 多维DP的常见错误与调试技巧踩过的坑全在这里多维DP的代码量普遍不大但调试起来经常让人怀疑人生。因为逻辑藏在状态转移里你很难靠“打个日志看看”来定位错误。这一节我把我刷题以来踩过和见过的所有常见错误整理成一张速查表再附上我自己最常用的调试技巧希望帮你少走一些弯路。5.1 高频错误速查表初始化、遍历顺序、边界处理错误类型具体描述典型后果解决思路初始化错误第一行第一列没有正确设置整个dp表从源头错起先手算长度为1的边界情况遍历顺序错误依赖状态在计算时还未填充结果随机或部分正确打印dp表检查依赖格子是否已填下标偏移错误字符串第i个字符误写成word1[i]而非word1[i-1]越界或结果莫名偏大记住dp[i]对应前i个字符状态定义混淆用下标表示而非前缀长度转移方程逻辑混乱重新提炼状态定义套“前i个”模板边界条件遗漏空字符串、长度为1的串未单独验证特定用例下报错提交前先测最小输入空间优化后逻辑错滚动数组时左上角值未保存结果近乎随机用完整二维表校准一维版本初始化错误在多维DP里尤其隐蔽因为大样例可能跑出正确答案但小样例一测就崩。比如63不同路径II你能想到处理障碍物但可能忘记处理“第一行第一列本身是障碍”的情况。这类边界case是面试官和评测系统最喜欢藏雷的地方你刷题的时候可以在纸上列出一组小输入把所有边界情况都覆盖一遍再写代码。5.2 打印dp表的调试大法用可视化打破“想当然”我调试多维DP用得最多的方法不是debugger而是手动打印dp表。做法很简单在双重循环跑完之后把整个dp矩阵用格式化的方式打印到终端然后拿一个小规模的输入自己拿笔在纸上把期望的dp表填一遍两张表一对比错误立刻现形。比如编辑距离有一个经典小用例word1 abcword2 yabd。手算期望的dp表前三行三列是什么第一行应该依次是0、1、2、3、3因为空串变成空串是0变成y是插入1变成ya是插入2变成yab是插入3变成yabd是插入4不对word2 yabd长度为4所以第一行是0、1、2、3、4。第二行的第一个值是1表示a变成空串需要删1个字符。这些小数你手一算代码对不对一目了然。打印dp表还有一个额外好处你会慢慢建立起“填表直觉”。填多了之后你看到一个多维DP题脑子里会自动浮现出一张二维表的形状转移方程不再是一个抽象的公式而是表里某个格子从哪个方向取值的问题。这种感觉一旦建立起来多维DP对你来说就再也不是难题了。5.3 独家小技巧先写暴力递归再改成DP彻底告别“不会推转移方程”接下来这个是压箱底的技巧我觉得它比任何模板都值得记住。如果你拿到一个多维DP题完全不知道转移方程怎么写那就先别想DP这回事直接写暴力递归。用递归去枚举所有可能的选择不管重复计算不重复计算先把正确性保证住。然后观察递归函数的参数——那些参数基本就是要放进dp里的维度递归函数里的状态转移逻辑就是转移方程的原型。以编辑距离为例暴力递归写法是这样的定义一个dfs(i, j)表示把word1前i个字符转换成word2前j个字符的最小操作数然后递归地去计算三种操作对应的情况。你会发现这个dfs(i, j)的参数i和j正好对应用二维表的行和列dfs内部的递归分支正好对应二维表里依赖的若干个前驱格子递归的终止条件正好对应dp数组的初始化。把递归改成自底向上的循环填表一个标准的DP代码就出来了。这个“先递归后DP”的路径比直接看题解学DP模板要踏实得多。因为你看题解学的是别人消化过的结论而递归是你自己枚举出来的过程。两种方式都能AC但只有后者能让你在遇到新题时不慌。6. 把多维DP刷明白之后面试官到底在考察你什么最后我想聊一个很多人刷题时容易忽略的问题热题100里的多维DP题面试官到底在测你什么只看答案的话你可能会觉得就是在考你“会不会这个算法”但实际上面试官考的是几层东西的叠buff。第一层是建模能力。拿到一个现实问题你能不能抽象出状态变量、找到转移关系、确定边界条件。这是动态规划的本质也是绝大多数非算法岗位的日常工作中根本不会专门练的能力。刷多维DP题本质就是在反复训练这种从复杂场景里抽取结构化模型的能力。第二层是代码功力。多维DP的代码不算长但它对下标处理、边界处理、代码整洁度的要求很高。一个能一次AC编辑距离的人大概率写其他稍复杂的业务代码时也不会出现低级越界和脏数据问题。这解释了为什么大厂面试官喜欢用DP题来筛人因为它是少数能把“思维能力”和“代码能力”同时考察到的题型。第三层是沟通表达。面试当场写DP题你要一边写一边讲什么状态下定义、为什么要优化空间、复杂度是多少。这是一个非常真实的团队协作模拟因为实际工作中你就是需要一边写代码一边跟同事解释思路。很多人在白板上写代码时手在抖、嘴在瓢不是不会写而是表达训练不够。所以我前面特意建议你刷完题后自己当面试官讲一遍目的就是把沟通这一层也练起来。多维动态规划在热题100里的题量不算最多的但它的战略地位在我看来远超其他专题。你把这块啃下来动态规划这个考点基本就拿捏了后面再遇到什么“打家劫舍III”“买卖股票的最佳时机”之类的一维DP变体反而会有一种下山打小怪的松弛感。我个人刷题的时候有个体会多维DP适合放在一天精力最充沛的时候刷千万不要在熬夜状态下碰因为它的调试过程对脑力要求真的高。每次卡题超过40分钟就果断看题解然后第二天再独立默写一遍。这种“先看后默”的节奏虽然慢但留得下来的内化率特别高。你可以试试看一周之后再来做热题100里的多维DP那种手到擒来的感觉会让前面所有的死磕都变得很值。