★ FEATURED ARTICLE 多维DP动规进阶路上绕不过去的一道坎。很多同学能轻松写出dp[i]、dp[i][j]但一碰上dp[i][j][k]就卡壳状态定义想不出来转移方程写不对循环顺序一调就错。这篇文章不打算从零科普动态规划而是聚焦多维DP最核心的三个问题维度怎么设计、转移怎么推导、空间怎么压缩顺便把我在实际刷题和项目里踩过的坑一次说清楚。适合已经掌握基础DP、但遇到三维以上状态就懵的同学照着这篇文章的思路走一遍你会发现自己也能把高维状态拆得明明白白。1. 多维DP到底难在哪先聊聊本质1.1 从一维到三维思维障碍到底出现在哪里先想一个问题一维DP你只需要关心“当前状态从哪里来”比如斐波那契的dp[i]只依赖dp[i-1]和dp[i-2]。到了二维你多了两个方向的抉择比如网格路径中dp[i][j]依赖上方和左方脑子里还能勉强画出表格。但到了三维甚至四维状态空间变得立体人脑没办法像二维表格那样直观地把所有状态同时铺开于是就开始乱。多维DP真正难的不是公式本身而是你要同时处理几件事第一三个维度之间有没有耦合关系耦合点就是转移方程的核心第二三层循环的嵌套顺序怎么安排哪一维该在外层、哪一维该内层第三哪些状态是天然无效的需要在代码里显式跳过。这三件事叠加在一起思维负担确实比一维二维高一个量级。我自己带人的经验是多维DP的障碍往往不是“不会写代码”而是“没有把问题拆成独立维度的习惯”。很多人上来就想要一个现成的dp定义却不愿意先花两分钟把题目里的所有变量列出来。变量和维度一一对应这个习惯一旦养成高维状态设计就成功了一半。1.2 多维DP的适用场景和前置能力多维DP到底解决什么问题一句话总结当问题存在多个相互独立的决策变量时就用多维状态把它们分别存下来。最典型的母题包括母题基础维度第三维/额外维含义背包类dp[i][w]前i件物品、容量wk件数限制或组别区间DPdp[l][r]区间左右端点k最多操作次数双序列DPdp[i][j]两个字符串位置k允许的误差次数网格路径dp[i][j]行列坐标t预算、时间或剩余步数这类状态在算法面试和竞赛里出现频率极高。想驾驭它们前置能力其实只有两条一是能熟练分析无后效性也就是确认“过去怎么来的”不影响“未来怎么走”二是能看出哪些变量是真正需要入状态的而不是所有变量一股脑全塞进去。具备这两个能力多维DP对你来说就不再是背题而是按套路拆解。2. 维度怎么设计从三个自检问题说起2.1 把所有决策变量先列出来维度自然就有了拿到题目我建议你第一步不要写代码而是在草稿纸上把所有“随着决策过程会发生变化、且影响最终答案的量”全部列出来。举个例子带预算限制的网格路径问题从左上角走到右下角每步只能向右或向下每个格子有费用总费用不能超过预算B求最小总花费或合法路径数量。这个问题里哪些量在变当前行i、当前列j、累计已花费的金额t。三个变量就对应三维状态dp[i][j][t]含义是“走到(i,j)且累计花费正好为t时是否存在合法方案”。到这里题目已经被翻译成DP语言了。这里有个非常重要的观点维度不是拍脑袋想出来的是题目里的约束条件一个萝卜一个坑对应出来的。每个在决策过程中存在多个可能取值的限制变量都有资格成为一维。反过来如果某个量在每一步都是固定值或者可以由其他维度直接推导得到那它就不该单独占一维。这个筛选过程本质上是在做“信息量最小化”也是多维DP设计中最值得刻意练习的部分。2.2 状态设计三问无后效性、可转移性、可更新性我每次设计完一个状态都会问自己三个问题通过这三个问题就能筛掉八成“看似合理实则错误”的状态定义。第一无后效性是否满足。以网格路径问题为例dp[i][j][t]只关心到达当前点后累计花了多少钱至于之前具体走了哪条路线完全不影响后面继续向右或向下走。这就是无后效性。如果某个状态含有“已经走过的路径信息”比如哪些格子被访问过那就不是纯DP能处理的得考虑状态压缩。第二转移是否可覆盖。也就是说当前状态能不能由已知的小状态明确推出来。网格路径的转移非常清晰要么从上方(i-1,j)来要么从左方(i,j-1)来所以t由t - cost[i][j]推过来。如果某个状态找不到确定的转移来源那状态定义多半有问题。第三最终答案能否从状态空间里提取。很多人状态定义对了最后取答案却取错位置。比如预算限制是“不超过B”如果你状态里存的是“已花费总额t”那答案应该遍历t 0..B取最小值如果你定义成“剩余预算t”那答案就是dp[n][m][B]。方向搞反AC无望。2.3 哪些变量不该进状态冗余与替换一个容易被忽略的坑不是所有变化的量都值得成为一维。有些变量之间存在线性关系已知一个就能推出另一个。比如某些题目里“已选物品数量”和“已占用容量”其实被物品的平均权重绑定这时只需要保留其中一个维度另一个在转移时临时算出来就行。另外如果一个值的取值范围特别大比如费用高达10^9你通常不应该把它当作状态维度因为数组根本开不下。这种时候要么换状态含义把大值域的数值放到dp数组的value字段里做“可行性判断”要么用贪心、二分配合DP把大值域问题转化为判定问题。我见过太多人明明想到正解雏形却死磕大值域维度结果空间超限解不出来。识别“哪些维度有资格进状态”和“哪些维度应该被替代”比盲目枚举维度重要得多。这一步想清楚往往能省掉一整个数量级的空间复杂度。2.4 空间压缩的两种主要手段滚动数组和维度合并多维DP最现实的痛点是空间不够。三维数组动辄几百万甚至上千万个元素稍微复杂一点就爆内存。空间压缩我常用两种手段。第一种是滚动数组。如果某一维在转移时只依赖上一层状态就把这一维大小压到2循环时用当前层和上一层交替覆盖。以网格路径问题举例如果转移只从(i-1,j)和(i,j-1)来那行列两个维度都可以滚动。滚动数组的关键是搞清楚覆盖顺序写反了会用新值污染旧状态。这个坑特别隐蔽我后面专门讲。第二种是维度合并。利用位运算或整型编码把一个“布尔状态集合”压缩成一个整数。状态压缩DP就是这么干的经典旅行商问题里的vis[mask][last]mask的二进制位表示哪些城市去过这就是把一维集合信息压进一个整型。多维DP里如果某个维度只是几个布尔取值比如“是否使用过某类操作”同样可以用位运算或枚举整型合并减少循环层数和空间。3. 带预算限制的网格路径问题从建模到AC完整拆解3.1 题目与数据范围三维状态是否有可行性为了把上面的设计思路落到实处我用一道完整题目走一遍流程。题目描述给定n行m列网格每个格子有非负费用cost[i][j]从左上角出发每次只能向右或向下移动一格到达右下角。要求整条路径总花费不超过预算B问满足条件的路径中总花费最小是多少如果不存在合法路径输出-1。数据范围设定为n, m 100B 1000cost[i][j] 100。这个范围下100 × 100 × 1001的三维数组约一千万个布尔元素内存勉强可行。做题前先估算状态空间这是多维DP最容易忽略的第一步。状态空间没算清楚就动手后面大概率白写。3.2 状态定义的分叉点为什么不能简单存最优值这个题目有个典型的分叉点值得停下来细说。表面看我们要求“最小总花费”直觉会想定义dp[i][j]为到达(i,j)的最小花费然后正常走最短路思路。但这个题不能这么做原因在于全局预算上限的存在。假设dp[i][j]存“到达(i,j)的最小花费”后续还要继续走当前花费小的方案到了后面可能被迫经过高费用格子总花费反而超预算而当前花费稍大的方案反而可能留出合适路径。也就是说局部最优不能推出全局最优因为预算约束贯穿整条路径。这种情况下你必须把“已花费总额t”作为状态维度而不是当作dp值。这正是多维DP的精髓当你发现某个变量无法被局部最优吸收时就把它显式地放进状态空间。3.3 转移方程与循环顺序t维方向最容易写反状态定义清楚后转移方程反而很简单。用0-based下标从起点出发累计花费t到达(i,j)那么上一步要么是从上方(i-1,j)来要么从左方(i,j-1)来且到达上一步时的花费是t - cost[i][j]。于是dp[i][j][t] dp[i-1][j][t - cost[i][j]] 来自上方 或 dp[i][j-1][t - cost[i][j]] 来自左方只要t cost[i][j]成立即可。这里的关键是t维度的循环方向因为t是从更小的t - cost[i][j]推过来的所以t一定要从小到大枚举。如果把t从大到小循环就会漏掉许多可行状态。i和j的循环方向则是顺其自然的网格路径本身有拓扑序从左上到右下普通双重循环即可。判断每个维度的更新方向是多维DP写代码前必须想清楚的一件事。我建议大家在草稿纸上标出每个维度的依赖箭头再决定循环顺序。3.4 初始化、边界处理与答案提取起点处理是个容易踩坑的细节起点格子的费用要不要算如果题目说起点费用也要计入那么初始化就是dp[0][0][cost[0][0]] true如果题目说起点终点费用不计则初始化要相应调整。这种一字之差的题目描述在实际比赛里能卡掉一大片人AC不了往往不是算法错而是语义理解错。边界方面t - cost[i][j] 0的情况必须在循环条件里排除不能让它落到数组负下标。实现时可以把t的循环写成for t in range(c, B1)直接从c起步天然避开负数。答案提取我再说一遍由于状态存的是“已花费总额t”预算限制是“不超过B”所以答案不是某个固定点而是遍历t 0..B找到第一个dp[n-1][m-1][t]为真的t。如果全都不为真返回-1。3.5 参考实现与手算测试用例用Python写一版最直观的实现方便对着看def solve(n, m, B, cost): # dp[i][j][t]: 到达(i,j)且花费总额为t是否可行 dp [[[False] * (B 1) for _ in range(m)] for _ in range(n)] if cost[0][0] B: dp[0][0][cost[0][0]] True for i in range(n): for j in range(m): if i 0 and j 0: continue c cost[i][j] for t in range(c, B 1): if i 0 and dp[i - 1][j][t - c]: dp[i][j][t] True if j 0 and dp[i][j - 1][t - c]: dp[i][j][t] True for t in range(B 1): if dp[n - 1][m - 1][t]: return t return -1写完代码后我喜欢立刻塞几个小数据手算验证。最简单的用例1×1网格B10cost[[5]]答案应为5。再来一个2×2网格B10cost[[1,5],[3,2]]两条路径花费分别是1528和1326答案应为6。如果B2两条路径都超预算应返回-1。这几个用例几乎能一次性把初始化、转移、答案提取三个环节全部验证到位。4. 多维DP高频变体识别背包、区间、双序列、状态压缩4.1 背包类容量、件数、价值三要素如何安排维度背包类是多维DP最经典的落脚点。01背包的基础状态是dp[i][w]表示前i件物品、容量w时的最大价值。一旦加入“件数恰好为K”的限制就变成dp[i][w][k]。件数维度的更新方向有讲究如果正推选一件物品会从k-1推到k所以件数维要从小到大循环但如果你用的是“逆推更新”的写法就必须保证访问到的k-1是上一轮状态而不是本轮被新值覆盖后的状态。什么时候用正序、什么时候用逆序是背包类多维DP最容易出错的地方我建议每种变体都自己在草稿纸上走一遍更新过程而不是死记结论。二维费用背包是另一个常见变化物品同时有重量和体积两种消耗dp[i][w][v]直接三维起步。这种题目的优化方向是看两种费用哪一个值域小通常选值域小的那个作为内层维度。4.2 区间DP叠加操作次数维度三维枚举的复杂度焦虑区间DP基础状态是dp[l][r]表示区间[l,r]的最优值。叠加一个限制维度比如“最多进行k次操作”就升级成三维dp[l][r][k]。这种类型的转移往往不是简单从相邻区间推过来而是枚举中间分割点dp[l][r][k] max(dp[l][mid][a] dp[mid1][r][k-a])其中mid和a都要枚举复杂度很容易到O(n^4)。因此这类题目的核心不是转移公式本身而是能不能用前缀最大值、单调队列等手段把某层枚举优化掉。我做过不少区间叠加次数的题最后卡人的基本都是优化而不是状态设计。4.3 双序列DP两个指针维度是骨架编辑距离是最典型的双序列朴素多维DPdp[i][j]表示字符串A前i个字符和字符串B前j个字符的编辑距离。如果题目增加“至多允许k次特定操作”就会升级为dp[i][j][k]。双序列DP的方法论是固定的先构建两个指针维度再根据“匹配、替换、插入、删除”等操作逐一写转移。我的习惯是在纸上把两个序列的依赖关系画成网格标出每个格子的转移方向再加第三维。画图这一步看起来笨但能避免七八成转移式写错的情况。4.4 状态压缩DP把集合信息压成一个整数状态压缩DP可以把逻辑上的多维状态编码成一维整数经典例子就是dp[mask][last]mask的二进制位表示已经访问过的城市集合last表示当前所在城市。这个写法本质上是把“每个城市是否访问”这一堆布尔维度合并成一个整数维度省空间也省循环层数。很多人把状态压缩和多维DP对立起来其实两者是递进关系多维DP把状态显式写在多个维度里而状态压缩是把部分维度编码后塞进更紧凑的结构。遇到n 20这种小规模集合问题优先考虑状态压缩遇到数值维度取值范围适中的问题优先考虑显式多维。搭配使用才能覆盖更多题型。5. 多维DP调试4个查错狠招和常见坑5.1 下标越界和初始化陷阱多维DP的越界问题不只是数组越界更多是逻辑越界。比如t - cost[i][j] 0时如果你没在循环里排除直接用负下标访问轻则运行时错误重则拿到错乱值。我的对策很朴素循环起点直接从cost开始从源头避免负下标。初始化方面如果你用“无穷大”表示不可达常犯的错是随手填一个很大的数结果在多次加法或比较后导致溢出或者恰好淹没了某个合法的较小状态。我的习惯是给INF一个明确语义值比如B1并且每次取答案时再显式过滤INF。这样即使INF参与运算也不会污染答案。5.2 滚动数组覆盖顺序错了会神不知鬼不觉滚动数组的经典坑是把当前层新产生的值覆盖到上一层旧值上而后面的状态又依赖那个旧值导致结果悄悄变错。这种错误不会让程序崩溃所以特别难发现。我判断覆盖顺序是否安全的方法很笨但很有效在纸上模拟一轮转移把每个新状态依赖的旧状态标出来再看滚动数组中这些旧状态有没有在依赖发生前被覆盖。如果有一处被覆盖就必须改成倒序更新或者把“源状态”和“目标状态”分别存到两个数组里。这个方法帮我抓出过很多次隐藏bug比盯着屏幕空想快得多。5.3 无效状态参与转移导致的错解多维DP里有很多状态根本不存在。比如网格路径问题中(3,3)位置花费为t0的状态就是无效的。如果状态值是布尔类型无效的false参与转移不会造成大问题但如果状态值是数值类型无效状态被设为INF后参与转移就可能把结果冲成INF 1之类的大数最终表现为“答案偏大”或“总是输出-1”。对策是在转移前显式判断源状态是否有效。具体代码就是在赋值前加一行if dp[src] ! INF:。这类问题很隐蔽排查时可以故意把INF设置成一个醒目的值比如-1让错误更容易暴露。5.4 高性价比的查错狠招暴力对拍、状态表打印、定向断流最后分享三个我用过无数次的查错方法按性价比排序。第一个是小数据暴力对拍。写一个纯暴搜解法和DP解法一起跑随机小规模用例比如网格路径问题里n5, m5, B10随机生成几百组数据结果不一致就说明DP有bug。这个方法几乎能覆盖所有隐蔽错误是算法题查错效率最高的一招。第二个是打印中间状态表。当某个用例错了把dp数组的关键截面打印出来对照手算结果找偏差。比如网格路径问题打印某一层的状态矩阵能快速定位是哪一步转移出了问题。第三个是定向断流测试。人为构造一个只能从单一方向转移的网格比如把某一列设计成“无法从左方进入”这时对应列的状态应该完全由上方转移而来。如果结果不对说明转移来源判断有误。这种测试比较进阶但诊断精度很高。6. 一些心得从“看得懂题解”到“自己推得出状态”刷题刷久了你会发现多维DP的套路其实是有限的。你不需要背几百道题而是把十几类母题的维度设计逻辑刻在脑子里背包问题里的容量和件数、路径问题里的坐标和预算、区间问题里的端点和操作次数、双序列问题里的两个指针。遇到新题先归入母题再按母题的维度设计套路去尝试成功率会高很多。我自己的练习路径是先把背包类所有变体做熟再做区间DP再做双序列最后上状态压缩。每一步都配合手动推演状态表的习惯而不是跑完AC就扔。状态表推演既能锻炼维度设计能力也为以后调bug打底这笔账怎么算都不亏。最后分享一个我在实际项目里总结出的经验多维DP的维度不是越多越好。能合并的合并能省掉的省掉能用贪心预处理削减的就先削减。状态空间最小化之后不仅内存得救连调试都会轻松很多。以后再遇到dp[i][j][k][l]这种东西先冷静问自己一句这四维真的都必要吗想清楚这个问题你的多维DP水平就真正进阶了。
阅读完成 · 觉得有帮助？
