动态规划写到第十一期算是把这条线彻底拉开了。前面聊过线性DP、背包、区间、树形……那些模型都有一个共同特点状态维度少转移顺序直观拿到题基本能顺着套。但真正让很多人卡住的是当状态从一维、二维跳到三维甚至更高以及状态本身从“一个数字”变成“一个集合”的时候——这就是这一期要说的三个高阶方向多维、排列与数学。多维DP不是单体的新模型而是一种状态维度的爆炸式增长排列类DP则是把“顺序”本身变成状态典型的落脚点就是状态压缩至于数学更像是给DP降维打击的武器公式推导、矩阵快速幂、概率期望、组合计数……用数学的方法把暴力枚举直接压缩成递推。如果你正在准备研究生数学建模竞赛或者被大学生数学竞赛的非数学组题目折磨再或者刷动态规划时觉得“会模板但不会建模”——这期内容大概率对你有用。先声明一句这期篇幅不短每一节我都按自己实战踩坑的顺序来写既讲“能过题”的写法也讲“为什么这么设计”的底层逻辑。1. 多维DP状态不是越多越好是“限制越多越立体重”1.1 多一维限制就是多一列“表格”先打一个比方。普通表格是二维的行和列飞书多维表格这类工具能让你按“项目”“月份”“负责人”三个维度同时统计本质上是把一个二维表扩展成了多维立方体。动态规划里的多维状态也是这个意思每多一条限制条件dp数组就多一个维度。最典型的例子是二维费用背包。普通01背包只有一个容量限制C所以状态是dp[j]表示容量为j时的最大价值但如果每个物品既占体积w[i]又占重量v[i]而背包既有容量上限C又有承重上限W这时候一个维度就不够用了。状态自然就变成三维数组dp[i][j][k]表示前i个物品在体积为j、重量为k时的最大价值。很多人第一眼看到这种题会觉得“状态这么多肯定写不出来”但其实逻辑完全没变。普通背包的转移是“选或不选”二维费用背包也是“选或不选”只是转移的时候同时扣掉体积和重量# 二维费用背包dp[j][k] 表示总体积为j、总重量为k时的最大价值 for item in items: wi, vi, ci item for j in range(C, wi - 1, -1): for k in range(W, vi - 1, -1): dp[j][k] max(dp[j][k], dp[j - wi][k - vi] ci)每次更新一个物品dp数组就要在整个(j,k)平面上扫描一遍复杂度是O(nCW)。这个复杂度看着吓人但它就是这一题的上界——你要遍历所有可能的体积和重量组合这个组合数本身是C乘W逃不掉的。多维DP的难点其实不在转移方程而在于“维度数”和“值域大小”的权衡。容量C和重量W如果是1000二维数组是100万轻松能开但如果你再加一个限制“每件物品最多选k次”“背包上最多放m件物品”状态就变成四维甚至五维内存直接爆炸。所以真正要练的是如何在多个限制条件之间做合并、删除、交换维度。1.2 多维DP的代价时间与空间的权衡我见过很多新手一上来就开四维数组结果连样例都跑不动。这里分享三个我在实战中常用的策略都是针对“维度爆炸”的。第一个策略是合并限制。有些限制看着是两个实际上可以变成一个。比如“体积不超过C且重量不超过W”这种双限制如果体积和重量在物理意义上同一量级有时可以把它们的乘积作为新限制或者把其中一个作为状态值域、另一个作为状态目标从而压缩维度。这不是万能药但值得先想一步。第二个策略是交换维度。经典的操作是把“限制量”和“目标值”互换。比如背包问题里容量最大是10^9显然没法开数组但价值总和最大只有10^4这时候可以定义dp[v] 达到价值v所需的最小容量最后倒着扫一遍找到第一个容量不超过限制的价值。这个技巧在二维费用背包、多维背包中特别常见能直接省掉一个大维度。第三个策略是滚动数组。所有只依赖上一层状态的动态规划都可以用滚动数组把“第i个物品”那一维滚掉。二维费用背包从三维变二维靠的就是这个。滚动数组的代价是你要格外小心遍历顺序每个内层循环都必须是倒序否则同一个物品会被重复放入结果就不是“01背包”而变成“完全背包”了。这个细节我后面在避坑章节还会重点讲。多维DP的核心认知就是一句话状态的维数对应限制数维数的值域对应限制的大小而你需要做的是在这个恐怖的笛卡尔积里找到一条能走通的路。2. 多维背包与多序列DP从模板题到建模实战2.1 多维背包的状态方程与滚动数组多维背包在竞赛里是一个固定考点尤其在研究生数学建模竞赛和算法笔试里很容易出现。它不一定是“二维费用背包”可能是“有件数限制的背包”“多组依赖背包”“多维重量背包”等等。但只要你把每个限制拆成独立维度状态转移的骨架是统一的。以“物品有体积w[i]和重量v[i]背包容量C和承重W求最大价值”为例完整模板可以写成def two_dim_knapsack(items, C, W): dp [[0] * (W 1) for _ in range(C 1)] for wi, vi, ci in items: for j in range(C, wi - 1, -1): for k in range(W, vi - 1, -1): dp[j][k] max(dp[j][k], dp[j - wi][k - vi] ci) return max(max(row) for row in dp)这里有个非常容易踩的坑内层两个循环必须都是倒序而且不能交换成先循环k再循环j交换是可以的只要两个都是倒序。但如果你把其中一个写成正序就相当于允许这个物品在“同一轮”里被多次选择答案直接错。我读代码时经常看到有人把j和k的顺序写反导致数组越界或答案偏大排查半天才发现是顺序问题。另一种偷懒但能大幅压缩内存的写法是直接把二维数组压成一维数组用“坐标映射”的套路# 将 (j, k) 映射成下标 idx j * (W 1) k这样做的唯一好处是内存连续、缓存友好在C里能显著提升速度。Python里如果追求可读性还是老老实实写二维列表吧。多维背包真正拉开差距的地方是两个限制之外的东西限制值域很大怎么办答案是“交换维度”。举个例子体积C10^9容量根本开不了数组但总价值maxV只有5000那就定义dp[v] 达到价值v所需的“最小体积重量复合代价”。于是问题变成在一个价值维度的数组里做01背包最后找满足双限制的最大v。这个思路说起来简单但遇到真题目能想到这一步的人不多。2.2 多序列的“维度对齐”难题从LCS到编辑距离多维DP的另一大分支是“多序列DP”也就是状态由多个序列的指针组成。最基础的是最长公共子序列LCSdp[i][j]表示第一个序列的前i个字符和第二个序列的前j个字符的LCS长度。如果上升到“三个序列的LCS”状态就顺理成章变成三维dp[i][j][k]# 三序列LCS for i in range(1, n1 1): for j in range(1, n2 1): for k in range(1, n3 1): if a[i-1] b[j-1] c[k-1]: dp[i][j][k] dp[i-1][j-1][k-1] 1 else: dp[i][j][k] max( dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1] )很多人在这一步就开始慌了为什么三序列LCS不能从“两序列LCS”直接推出来因为两个序列的公共子序列不一定被第三个序列包含三个序列之间的匹配关系要同时对齐所以必须三维。多序列DP的复杂度也是维度乘积灾难的直接体现。两个长度100的序列二维数组是1万三个长度100的序列三维数组就是100万四个就是1亿内存和时间全炸。因此在实际竞赛里三序列LCS一般只敢出在长度50左右四序列及以上几乎不会出现除非能压缩状态。还有一类多序列DP是“字符串对齐”例如编辑距离、正则表达式匹配、字符串通配符匹配。编辑距离的转移是dp[i][j]由dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]三种来源推导本质上也是两个指针在字符串上移动的过程。这类题你要关注的是“空串边界”的处理dp[0][j]j, dp[i][0]i很多人初始化和转移搞混导致边界值全是0。多序列DP的经验总结状态维度就是指针个数指针个数越多转移越“肉眼可读”但也越容易超时优化靠的是把多余的指针合并成一个更抽象的贪心状态或者用自动机压缩。3. 排列与状态压缩当“顺序”成为状态3.1 为什么排列问题要“把状态塞进一个整数”在我接触DP的第一年最怕的就是排列相关的问题。原因很简单排列的状态是“一组元素的顺序”你总不能开一个数组dp[全排列]吧。比如n10全排列数是3628800还能勉强枚举n15全排列数是1.3万亿直接没救。但如果你把“当前已经使用了哪些元素”用一个二进制数来表示状态数就从n!降到了2^n。这就是状态压缩DP也就是常说的状压DP。它把排列问题强行变成了“子集问题当前顶点”的组合状态。经典的TSP旅行商问题是这样建模的dp[mask][i]表示已经访问的城市集合为mask且当前站在城市i时走过的最小总距离。转移是枚举下一个未访问城市j# TSP 状压DPC为城市个数 dp [[inf] * C for _ in range(1 C)] for i in range(C): dp[1 i][i] 0 for mask in range(1 C): for i in range(C): if not (mask i) 1: continue if dp[mask][i] inf: continue for j in range(C): if (mask j) 1: continue nmask mask | (1 j) dp[nmask][j] min(dp[nmask][j], dp[mask][i] dist[i][j])答案通常是min(dp[(1 C) - 1][i] dist[i][0])也就是所有城市都访问过最后回到起点的最短路径。这个模型能解决一大批“排列顺序最优”的问题而且它有一个很妙的地方mask本身代表了“集合”i代表“最后的落点”两者一组合就完美刻画了“当前排列的前缀”。你不需要关心前面城市的先后顺序只需要知道哪些城市已经用过、现在站在哪里因为之后的状态转移只用得到这两个信息。这就是状压DP的精髓丢掉多余的历史保留最小充分状态。3.2 排列计数从“枚举全排列”到“按位构造”除了“排列最优”还有一类问题是“排列计数”。比如“n个人站成一排要求相邻两个人不能来自同一个小组问有多少种站法”。如果用全排列暴力枚举是n!但状态设计为dp[i][j] 当前安排了前i个位置且最后一个位置是第j组的人方案数就能以O(n*k)解决# dp[i][j]前i个位置最后一个是第j组的方案数 dp[1][j] cnt[j] for i in range(2, n 1): for j in range(k): for p in range(k): if p ! j: dp[i][j] dp[i-1][p] dp[i][j] * cnt[j] # 模拟组内不同人的选择这里的转移要格外小心“组内不同的人”带来的乘法因子。如果不乘cnt[j]你算的是“组序列”的数量而不是“具体人到人”的排列数。这个细节我在机试里吃过亏后来养成了习惯凡是带“不同个体”的排列计数在状态转移中必须显式乘上个体数。还有一种和数学关系更紧密的排列计数是用“插入法”构造DP。典型例子是求“相邻元素之差的绝对值不超过k的排列数”。思路是把数字按从小到大逐个插入到已有排列的空隙中每次插入时维护“当前排列中相邻差合法”的状态。因为插入一个更大的数字只会影响它左右两个相邻关系所以状态可以设计成和“当前排列中不合法相邻关系的数量”有关最后等于0的数量就是答案。这种DP的转移天然带组合数如果你平时组合数学底子好写起来会很顺手。我在刷题时还遇到过一个名字很吓人的题“正则二分图的最长邻居排列数”。第一次看到我甚至不确定它是不是一个DP题。后来拆解发现它本质上是给二分图的一侧顶点定一个排列顺序另一侧顶点的某些匹配属性跟着变化需要最优排列——建模以后就是典型的状压DP状态是“当前已确定顺序的顶点集合”转移是“下一个选哪个顶点会带来多少收益”。所以遇到“排列”类题目先别被唬住把目标拆成“前缀状态最后一位”的组合往往就能落到DP框架上。3.3 状压DP的代价与适用边界状压DP也不是银弹它的状态数是2^nn超过20时即使乘上状态转移的n也接近两千万甚至上亿已经接近极限。如果你看到n25、30那大概率不是裸状压而需要折半枚举、剪枝或数学优化。实战中还有一个很有用的经验如果mask和前一个位置i的组合冗余可以想办法去掉i维。比如有的排列计数只关注“当前集合”而不关心最后一位那么dp[mask]就够用反之如果转移依赖最后一位就必须保留i维。能用1n表示的状态别开2^n*n的数组能省就省因为内存和时间往往是同步膨胀的。另外状压DP的位运算优先级很坑。在C里(mask i) 1一定要加括号mask | (1 j)也一定要加括号否则编译器会按位运算优先级低于比较运算的规则把你的表达式解析成完全另一个意思。我见过不止一个选手因为少写括号调了一晚上最后发现是位运算优先级背锅。4. DP与数学的联姻公式推导、矩阵加速与期望4.1 暴力枚举 → 推导公式 → 数学构造的完整链路动态规划和数学在这两年几乎成了竞速圈的一种固定搭配。很多DP题直接状态转移能过70%的数据点剩下30%的大数据必须靠数学优化或者干脆用公式代替DP。我印象很深的一道题是“统计[L,R]区间内所有整数的数位和之和”。朴素做法是遍历区间内每个数O(R-L)直接超时哪怕用数位DP也要O(len*10)的状态。但如果你把每一位的贡献拆开用公式算每一位上0~9各出现多少次复杂度能压到O(len^2)甚至O(len)连DP都不用写。这就是“暴力枚举 → 推导公式”的典型链路。类似的情况在卡特兰数上更明显。n个节点的二叉搜索树数量可以用DPdp[i] sum(dp[k] * dp[i-1-k])O(n^2)能算。但如果你知道答案就是C(2n,n)/(n1)那就直接O(n)求组合数大n时还能用费马小定理求逆元。数学在这里不是炫技而是实实在在优化复杂度。所以我给读者的建议是遇到DP题先把暴力和DP递推都写出来然后问自己两个问题——这个递推能写成闭式公式吗这个递推能用矩阵快速幂优化吗如果能那你就比只会写模板的人快了一个量级。4.2 线性递推与矩阵快速幂把O(n)变成O(log n)矩阵快速幂是最典型的“DP数学化”手段。它适用的场景是dp[n]只依赖于之前固定的若干项且转移是线性的。最简单的例子是斐波那契数列F(n) F(n-1) F(n-2) F(0) 0, F(1) 1把它写成矩阵形式[F(n) ] [1 1] [F(n-1)] [F(n-1)] [1 0] [F(n-2)]于是F(n)就等于转移矩阵的n次方乘以初始向量矩阵快速幂把O(n)的循环压缩到O(log n)。当n达到10^18时普通递推永远算不完而矩阵快速幂眨眼就能出结果。把DP写成矩阵的关键是找出“状态向量”和“线性转移系数”。状态向量把dp[n], dp[n-1], ..., dp[n-k1]打包成一个k维向量转移矩阵就是那k个递推系数。常见的线性递推还有包含常数项、前缀和的状态这时候只要在向量里多塞几个“常数状态变量”就能处理。这里有个很容易被忽略的角落只有当转移系数是常数时矩阵快速幂才适用。如果系数随下标变化比如dp[n] n*dp[n-1] dp[n-2]那就不能直接套矩阵需要配合多项式技巧或分段处理。4.3 概率期望DP把“运气”也变成状态概率和期望DP是数学建模竞赛的常客但也是最容易让人懵的DP类型。它难在两点状态本身不一定是“路径长度”“价值”这种确定量而是“期望次数”“概率值”转移时常带后效性甚至形成环。先从最简单的无环模型说起。一个经典问题一枚硬币正面概率p反面概率1-p直到抛出正面为止问期望抛掷次数。设E为期望次数第一次抛掷一定有1次然后分两种情况E 1 p*0 (1-p)*E解方程得E 1/p。这种“自己转移到自己”的模型本质是带自环的期望DP解决方式是设未知数解方程。带自环的简单问题能列一个方程搞定但一旦状态多了就变成线性方程组需要高斯消元。期望DP最常见的建模方向是“从目标状态倒推”。比如“从起点出发每次以一定概率走到不同格子问到达终点的期望步数”通常设dp[i]为“从第i个格子到终点的期望步数”然后从终点向前倒推dp[终点]0dp[i]等于所有后继格子的期望步数按概率加权再加1。这里加1代表当前这一步已经走了。我记得在2025年研究生数学建模竞赛的热门题单里很多问题都是“随机游走期望到达时间”这类题如果状态空间不大直接用高斯消元即可如果状态空间大就要找马尔可夫链的对称性压缩状态。压缩状态的思路和多维DP的合并维度完全一致核心都是“发现等价类”。期望DP的代码调试比普通DP烦得多因为你有小概率踩中浮点误差。建议所有累加操作都用double不在中间过程做精度截断最后再四舍五入。如果涉及取模形式的期望比如要求对1e97取模的期望值那就需要用到模逆元和模意义下的高斯消元这个坑更大新手慎入。5. 实战中的坑位排查与自查清单5.1 高频易错点速查表写到这一期我把自己和身边朋友在实战中踩过的坑整理成一个速查表不一定全面但绝对高频问题类型典型症状解决办法多维背包遍历顺序错误答案偏大或物品被重复选所有“选一次”维度的循环都要倒序多维数组初始化错误期望的边界是0却全是inf把dp[0][0][...]按照语义精确初始化为0或1状态压缩位运算优先级表达式被解析成错误结果(mask i) 1、mask排列计数漏乘个体数算出的方案数远小于正确值转移乘上该组可用人数cnt[j]期望DP除零错误程序跑着跑着崩了转移前检查分母是否可能为0矩阵快速幂初始矩阵写反结果在n1时就错了先手算n1、2验证矩阵方向滚动数组正序误用物品被无限次选择内层所有限制维度均倒序遍历维度过大硬开数组内存超限尝试交换维度、滚动数组或直接公式这张表我每次比赛前都会扫一眼。看似简单但“知道”和“在紧张状态下不踩坑”是两码事。5.2 一套亲测有效的自查清单做完一道高阶DP题不要急着提交先走一遍我下面的自查流程能省掉大把罚时。第一步检查状态定义是否最小充分。把状态里的每个维度拿出来问自己后续转移真的需要这个信息吗不需要就删掉。比如TSP里mask和i缺一不可但有些题里“当前走到哪里”其实可以由mask的某个bit直接推出那i维就是冗余的。第二步检查转移是否覆盖了所有来源。多维DP最常见的错误是漏掉一种转移来源。比方说三序列LCS除了三个指针同时匹配的情况还要考虑“第一个不匹配”“第二个不匹配”“第三个不匹配”三种单向推进。只写一种推进方式的代码基本都会超时或漏解。第三步检查边界和空状态。dp[0][0][0]或者dp[0][empty]这个位置是整个动态规划的种子。种子错了后面全错。建议在纸上手模一遍最小规模样例比如n0、n1、n2的情况再开跑代码。第四步检查复杂度上限。写代码前就心算一下维度乘积估算内存和循环次数。如果超限立刻转向优化思路不要抱着“也许数据小能过”的侥幸心理。这套自查流程看起来笨但能帮你把提交前“自我怀疑”的时间大幅缩短尤其是比赛分秒必争的时候。我个人对高阶DP的实际体会是多数人不是败给题目而是败给状态设计。状态设计没有一个万能公式但有一个可以练习的起点——把题目里的每个限制条件列出来先让每个条件占一个维度然后再想怎么合并、压缩、交换维度。能省维数就省不能省就滚动数组硬扛实在扛不动就换数学工具。反复这么练从二维到三维从排列到期望手感会慢慢建立起来。最后再分享一个小技巧遇到不会的高阶DP题先看能否用暴力枚举跑通小数据再用小数据的手算结果反推状态转移方向。很多看似复杂的多维DP其实都是从一个简单的“选或不选”“往左还是往右”的决策演化出来的。把这个决策找出来状态设计就完成了一半。