dp复习与dp优化状态设计是骨架转移加速才是灵魂动态规划在算法里属于那种“学过很多遍每到用时依然会卡壳”的知识点。我刷题、带新人、准备面试这么久反复看到同一种情况状态定义想清楚了一写转移就超时或者小数据能过数据规模一大直接内存爆炸。这篇文章就是一篇dp复习与dp优化的实操总结目标很直接——先帮你把动态规划的基本功重新焊牢再帮你把几种最常用的优化手段讲透包括滚动数组、状态压缩、前缀和优化、单调队列优化、斜率优化、四边形不等式优化和分治dp优化。适合三类人看正在系统复习dp准备算法竞赛的人、面试前临时抱佛脚想快速把背包和区间dp捡起来的人以及做工程时状态多到内存放不下、转移慢到跑不动的开发同学。全文不会有玄学所有优化方法都配有可运行的示例和复杂度对比。顺便说一句dp这个缩写在不同的领域代表完全不同的东西一些人谈dp第一反应是“数据并行”比如大模型训练里的PP、TP、DP分法但在这篇文章里dp就是动态规划是算法里那个用子问题答案拼出大问题答案的经典思想。如果看标题点进来是为了找数据并行那这篇不对路请绕道如果你要找的是算法里的动态规划优化那往下看保证有收获。1. dp复习先把状态、转移、边界这三件事做扎实1.1 为什么说“状态定义决定复杂度上限”动态规划的基础框架其实只有三句话定义状态、写出转移、确定边界。任何dp题都逃不开这三件事而99%的dp问题做不出来不是转移公式不会推而是状态定义从一开始就歪了。状态定义决定了整个算法的复杂度上限。同样一个问题用一维状态还是二维状态决定了空间是O(n)还是O(n^2)转移是O(1)还是O(n)。这一步定错了后面再优化的空间都很有限。所以复习dp我习惯先让大家反复练“把问题翻译成状态”这个动作你关心什么维度就保留什么维度你不关心什么维度就千万别往状态里塞。举个最典型的例子0/1背包。物品数量和背包容量是两个天然维度状态定义就是dp[i][j]表示前i个物品在容量j下的最大价值。这个定义一出转移几乎写死第i个物品要么不选继承dp[i-1][j]要么选从dp[i-1][j-w[i]]加上价值v[i]推过来。很多人觉得背包简单但就是这种基础模型里藏着dp优化的全部起点——因为二维数组明显有空间冗余因为一维转移明显可以省掉一重枚举后面的滚动数组优化其实都是在“压”这个定义。1.2 用0/1背包和区间dp重建手感和套路复习dp我最推荐的路径是先把线性模型打通再把区间模型打通。线性模型指的是背包、LIS、LCS这一类特征是状态天然沿着数组下标推进转移只依赖前面的位置区间模型指的是石子合并、矩阵链乘这一类特征是状态是区间[l, r]转移要枚举中间分割点。两类模型覆盖了dp入门到进阶的大部分场景。以区间dp最经典的“石子合并”为例。有n堆石子排成一排每次只能合并相邻两堆合并代价是两堆重量之和问把所有石子合并成一堆的最小总代价。状态定义是dp[l][r]表示合并区间[l, r]的最小代价转移是枚举一个分割点kdp[l][r] min(dp[l][k] dp[k1][r]) sum(l, r)这里sum(l, r)是区间重量和用前缀和O(1)算。如果暴力枚举k复杂度是O(n^3)。n200的时候能跑n2000直接爆炸。这个题就是四边形不等式优化最经典的靶子后面我会用一整节专门讲。新手写区间dp最容易错的是遍历顺序。很多人习惯直接枚举l和r结果发现用到的子区间还没算过。正确做法是先枚举区间长度len再枚举左端点l右端点r l len - 1。记住这个顺序问题后面会省很多调试时间。注意dp复习阶段最重要的不是背题而是建立一个自查清单——状态定义是否覆盖了所有决策维度转移是否覆盖了所有可能边界值是否会导致数组越界这三条检查完再谈优化。2. 空间维度的优化滚动数组与状态压缩2.1 滚动数组一维数组解决0/1背包的流程与逆序原因先说滚动数组。它的思想特别朴素如果dp转移只用到了上一层的状态那就不需要保留所有层开两个数组轮换就行。空间从O(n^2)降到O(n)这是性价比最高的一种dp优化几乎零成本、零风险。0/1背包的滚动数组是关键中的关键因为它是“逆序更新”的典型。为什么必须逆序因为一维数组在更新dp[j]时dp[j - w[i]]如果已经被本轮更新过就等于把同一个物品装了两次这就不再是0/1背包了。逆序遍历能保证dp[j - w[i]]还是上一轮的值这样每个物品最多被选一次。下面这段代码是最标准的写法// 0/1背包一维滚动数组 vectorint dp(C 1, 0); for (int i 1; i N; i) { for (int j C; j w[i]; j--) { // 注意逆序 dp[j] max(dp[j], dp[j - w[i]] v[i]); } }而完全背包恰恰相反每个物品可以选无限次那就要正序遍历让dp[j - w[i]]能被本轮结果覆盖这样才能实现“同一个物品可以反复取”。很多新手在这里搞混一遍遍wa还不知道错在哪。我的经验是写滚动数组背包前先在注释里标明“0/1逆序、完全正序”六个字这是最容易记住也最容易忽视的细节。2.2 状态压缩dp用整数表示集合以存储换时间状态压缩是另一类空间与时间的双重优化典型场景是集合类问题比如旅行商问题。n个城市每个城市去没去过是一个0/1集合信息。如果把“去过哪些城市”直接用数组维度表示那需要2^n个状态这在n 20时是可行的因为用整数位表示集合能大幅压缩存储和转移成本。以旅行商问题为例状态定义是dp[S][i]S是整数二进制第k位表示城市k是否已访问i表示当前在哪个城市。转移枚举下一个没访问的城市jdp[S | (1 j)][j] min(dp[S | (1 j)][j], dp[S][i] dist[i][j])这种写法的核心价值是“以空间换时间”2^n个状态每个状态转移O(n)总复杂度O(n^2 * 2^n)。n15以下随便跑n20时12亿次左右会吃力n25以上就不太可行了。实际工程中这种优化常见于路径规划、资源分配等离散组合场景。状态压缩dp有三个坑第一个是位运算优先级很多人写 S | (1 j) 时忘了加括号优先级错了直接出bug第二个是数组大小2^n * n在n较大时内存爆炸开数组前一定要算清楚第三个是初始状态比如TSP的起点是dp[1][0] 0剩下全是无穷大漏了初始化会让答案变成0或者负数。3. 转移阶段的加速前缀和、单调队列与二进制优化3.1 前缀和优化把O(n)的枚举变成O(1)查询dp优化的第二个方向是优化转移也就是让“从哪些状态转移过来”这个枚举过程变快。最常见、最容易上手的就是前缀和优化。适用场景很典型转移公式里要对一段连续区间的dp值求和或求最值而且这个区间端点随i单调变化。举个例子一维dp要计算某个前缀和dp[i] max(dp[i-1], dp[i-2] a[i])这里其实不需要优化因为只依赖前两个。但如果是下面这种转移dp[i] max( sum(dp[j]) for j in [i-k, i-1] ) cost[i]每一轮都重新遍历区间复杂度是O(nk)。如果k很大直接用前缀和或滑动窗口就能把求和部分降到O(1)。前缀和适合求和滑动窗口适合维护区间最值本质都是“把重复计算过的信息存下来”。我见过很多人在自己写的dp里明明有一段区间和是重复计算的却每次都去循环累加完全没有意识到可以预处理前缀和。这里给一个通用经验任何dp转移里出现“对j循环求和”的痕迹第一步就看看这个和能不能用前缀和表示出现“对j循环取max/min”的痕迹第一步就想想这个最值能不能用单调队列维护。3.2 单调队列优化滑动窗口与一类定长转移单调队列优化的本质是维护一个区间内的最值候选集合并且保证候选集合里的值按某种单调性排列。最典型的场景是滑动窗口最大值。dp转移里如果出现“长度不超过k的连续段的最优值”而且i从小到大推进、窗口也在推进那单调队列就能把每个状态的转移从O(k)降到O(1)。一个常见的dp模型是dp[i] max(dp[j] val(j))其中j在区间[i-k, i-1]内。如果val(j)只和j有关那么每个j进入窗口时就可以比较它与队尾元素在“未来”的优劣把永远不可能成为最优的旧元素出队。队列里存的是候选下标窗口滑动时先弹出过期下标再维护单调性最后队头就是当前最优。我写单调队列优化时有三个习惯第一队列里存下标而不是存值因为要用下标判断是否过期第二先“出队过期元素”再“入队新元素”顺序不能乱第三写完后用一个几十个数据的小样例人工推导一遍因为这类题一旦窗口边界算错基本只能靠对拍发现。这个优化在实际做题中极其常用尤其是滑动窗口类问题、多重背包优化、以及一些二维dp的降维转移里。3.3 多重背包的二进制拆分多重背包是背包家族里最容易出问题的成员。它有n种物品每种有数量s[i]个直接按0/1背包展开成每个物品跑一遍复杂度是O(N * C * s_max)遇到s很大的数据会直接超时。二进制拆分的思路很经典把s[i]分成若干个2的幂次和一个余数的组合比如13拆成1、2、4、6这四个数通过组合能表示1到13的所有整数。然后用拆出来的这些“新物品”跑0/1背包就能覆盖原问题的所有选取数量。复杂度从O(NCs)降到O(NClog s)。这种优化本质上是一种“等价变换”把指数级的组合空间压缩成了对数个基础物品。类似的思路也出现在快速幂和稀疏表里都是利用二进制表示来减少冗余。写过几道多重背包变体题之后你会慢慢形成这种直觉看到“有数量限制的选择问题”先想能不能用二进制的角度做等价拆分。4. 决策优化斜率优化与四边形不等式4.1 斜率优化从暴力枚举到凸包查询斜率优化是整个dp优化里概念最难、但一旦掌握收益极大的一类。它适用于一类特殊转移——决策之间存在“比值关系”可以把转移方程转化成直线求截距的问题。比如很多一维dp转移长这样dp[i] min( dp[j] (sum[i] - sum[j])^2 C )直接枚举j是O(n^2)n到10万就卡死。把式子拆开dp[i] min( dp[j] sum[j]^2 - 2*sum[i]*sum[j] ) sum[i]^2 C把sum[j]看作x坐标把dp[j] sum[j]^2看作y坐标把-2*sum[i]看作斜率k问题就变成了在所有已处理的点上找一条斜率为k的直线使其截距最小。如果这些点形成了凸包结构最优决策点会在凸包上移动于是可以用单调队列维护一个凸壳每个状态O(1)转移。斜率优化最难的地方不是公式推导而是理解“为什么能用凸包”。我的经验是用几何直觉去记忆。把每个j的二元组画在坐标系上然后想象一条斜率固定的线从下面往上推最先碰到的点就是最优决策。一旦这个画面在脑子里成立了代码只是几何过程的翻译。写斜率优化时有个比较麻烦的细节判断斜率时要避免除法带来的浮点误差。标准做法是把比较两个点斜率的过程转成叉积形式也就是移项后用long long相乘来比较。这里贴一段常见写法// 斜率优化维护下凸包求最小值 long long Y(int j) { return dp[j] sum[j] * sum[j]; } long long X(int j) { return sum[j]; } long long K(int i) { return 2 * sum[i]; } bool check(int a, int b, int c) { // (Y(b)-Y(a))/(X(b)-X(a)) (Y(c)-Y(b))/(X(c)-X(b)) // 转为乘法避免浮点 return (Y(b) - Y(a)) * (X(c) - X(b)) (Y(c) - Y(b)) * (X(b) - X(a)); }这种基于叉积的写法在竞赛里是标配在工程里也建议沿用因为浮点误差在数据量大时真的会让人排查到怀疑人生。斜率优化适用的题目特征非常明显转移方程里有二次项或者转移代价与两者的乘积有关出现这类项时就要警惕这题多半是斜率优化的靶子。4.2 四边形不等式区间dp的经典加速四边形不等式优化是区间dp爱好者的福音。它解决的核心问题是对于形如 dp[l][r] min(dp[l][k] dp[k1][r]) cost(l, r) 的转移如果满足“四边形不等式”和“单调性”两个条件那么最优分割点k会随着区间移动而单调移动于是可以在枚举k时收窄范围。以石子合并为例如果直接枚举所有k复杂度O(n^3)。优化后每次枚举k的范围从[l, r-1]缩成[opt[l][r-1], opt[l1][r]]其中opt记录每个区间的最优分割点。这个收窄看起来不多但总复杂度能摊还降到O(n^2)这在大数据量下是质的提升。判断一个题能不能用四边形不等式的标准我总结为三步第一步用暴力程序跑小数据把每个区间的opt值打出来第二步肉眼检查opt数组是否满足“对同一个左端点opt随右端点单调不减对同一个右端点opt随左端点单调不减”第三步如果单调性成立再用四边形不等式的理论条件验证或者直接优化后用对拍确认。实际做题中很多时候题目不会明确告诉你“满足四边形不等式”需要靠打表观察这也是这类优化不太为人熟知的原因。4.3 分治dp优化与决策单调性验证分治dp优化是另一种利用决策单调性的手段适用于dp[i][j] min(dp[i-1][k] cost(k1, j)) 这类分层转移问题也就是常说的“分治优化dp”。它的核心思想是如果每一层的决策点具有单调性那么计算这一层的所有dp值时可以用分治的方式每次先算中点的最优决策再确定左右两半的可选决策区间递归处理。复杂度从O(n^2m)降到O(nm*log n)。分治dp优化和四边形不等式优化是“同源不同术”四边形不等式通过记录opt来收窄枚举范围分治dp通过在决策值域上分治来减少枚举量。使用分治dp的前提还是决策单调性。很多人在做这类题时忽略了一个前置验证步骤先写一个暴力版本取几组随机数据验证决策点确实单调再上分治优化。这一步虽然额外耗时但能避免你在一道不符合单调性的题上浪费整晚。我个人的经验是决策单调性是所有决策类优化的“准入证”。没有单调性斜率优化、四边形不等式、分治dp全都不能用强行用会得到错误答案。所以无论哪种优化动手前先验证单调性是我反复强调的准则。5. dp优化选型速查与避坑实操5.1 优化方法选择速查表把前面几节的内容汇总成一张速查表方便在实际做题或工程中快速定位该用哪种优化。优化类型适用场景典型问题复杂度收益实现难度滚动数组转移只依赖前一层0/1背包、LCSO(n^2)到O(n)低状态压缩dp集合选择类问题TSP、子集划分空间大幅压缩中前缀和优化转移中出现区间求和划分型dpO(n)到O(1)低单调队列优化转移中取定长窗口最值滑动窗口、多重背包O(nk)到O(n)中二进制优化多重背包类数量选择多重背包O(ncs)到O(nclog s)低斜率优化转移含乘积/二次项任务安排、划分数组O(n^2)到O(n)高四边形不等式区间dp最优分割点单调石子合并O(n^3)到O(n^2)中分治dp优化分层转移且决策单调邮局问题、区间划分O(n^2m)到O(nm*log n)高这张表是我自己写题时反复用的自查清单。看到一道dp题先判断它的瓶颈在空间还是时间空间不够用滚动或状态压缩时间不够就按转移公式的特征去匹配优化手段。匹配的优先级是先看有没有重复计算的区间和或最值再看有没有乘积项或决策点单调性最后再决定上不上高级优化。5.2 调试dp的三种手段对拍、打表、样例走查dp题调试起来比普通题痛苦因为状态空间大、转移分支多错误往往藏在某个状态的边界条件里。这里分享三个我长期使用的调试手段。第一个手段是对拍。写一个暴力版本比如直接递归加记忆化再写一个优化版本用随机小数据反复比较两者输出。对拍能覆盖你没想到的边界分支。实现方式很简单生成随机数组暴力跑一遍优化跑一遍对比结果不同就停下来手动分析。第二个手段是打表。把dp数组在关键转移点的值打出来看尤其是中间状态的输出。比如滚动数组优化后把每轮更新后的dp数组打印出来人工对照转移方程推一遍很多问题立刻能发现——到底是数组越界了、顺序错了还是初始值不对一眼就清楚。第三个手段是样例走查。找一个最小的能复现问题的数据比如n3、容量为5的背包然后手动在纸上跑一遍你设计的转移流程。这个方法虽然“古老”但定位问题极其高效尤其是区间dp的遍历顺序问题纸上走一遍比盯屏幕半小时好使。5.3 常见问题与排查记录当我停止刷题、开始带别人写dp优化时发现新手容易踩的坑高度集中。我把它们整理成一份排查记录这几条每一条都是我亲眼见过的真实事故。数组维度混乱是最常见的问题。滚动数组优化把一个二维状态压成一维后很多人就分不清当前值是“本层”的还是“上一层”的。我建议在代码注释里明确标记“哪个循环代表层数哪个循环代表容量”同时每一轮更新前把数组打印出来确认一遍直到手感形成。遍历顺序错误是背包类问题的重灾区。0/1背包必须逆序完全背包必须正序这是两个完全相反的规则混一次就错一次。我自己的习惯是每写一个背包题都会先写两行注释这是0/1背包j循环逆序这是完全背包j循环正序。这两个注释帮我避免了无数次无谓的调试。边界索引错误在区间dp里出现频率极高。区间[l, r]中r l len - 1很多人直接把r写成l len导致数组越界。还有枚举k的时候k的范围是[l, r-1]但有人写成[l, r]重复计算了空区间。排查这类问题时我最常用的手段是在转移处加一条assert保证下标合法跑一遍数据就能精准定位。还有一类问题是“没用long long”。dp优化后计算量变大中间乘积很容易超过int范围斜率优化里尤其明显。凡是涉及乘法、累加的状态转移建议直接用long long代价只是很小的内存增加却能避免大量溢出bug。最后一个问题是“优化方案没有先用暴力验证正确性就上线”。很多人拿到一道符合四边形不等式特征的题二话不说就直接写优化版写完发现wa了但又不知道是优化写错了还是这题根本不满足优化条件。我的建议永远是先用记忆化暴力版本跑通小数据确认状态和转移都正确然后再上优化如果优化版有bug用暴力版对拍定位而不是对着代码苦想。末尾再分享一点个人经验动态规划优化这条路我走过不少弯路。最开始学斜率优化时我对着公式抄了三天代码抄到能默写但其实根本没懂为什么一条直线往凸包上碰就能决定最优决策。后来静下心画图、用几十组数据手动模拟那个“砰”的点扎进凸包里的瞬间我才真正觉得通了。所以我想说dp优化不是背诵模板它的每个优化手段背后都对应一种对问题结构的观察——滚动数组看到了依赖的局部性单调队列看到了窗口的滑动性斜率优化看到了决策的几何性四边形不等式看到了分割点的单调性。如果你现在卡在某道dp优化题上我的建议很简单写暴力、验证单调性、画图、对拍这四步做完大部分疑惑都能解开。优化技巧本身是有限的但问题结构千变万化真正值钱的是你判断“该用什么优化、为什么可以优化”的能力。这个能力只能靠大量动手积累没有捷径。最后再提一个小技巧准备一个dp优化选题本每遇到一种新优化就记一道代表题标清楚“问题特征”、“优化原理”、“复杂度变化”和“易错点”。等积累到三四十道题之后你会发现自己看到新题的第一眼就能大致判断出该用什么套路那种感觉很上瘾。这也是我从一个见到dp就头疼的初学者慢慢变成一个“遇题先想优化”的老手的过程。
DP复习与优化：状态设计是骨架，转移加速才是灵魂
dp复习与dp优化状态设计是骨架转移加速才是灵魂动态规划在算法里属于那种“学过很多遍每到用时依然会卡壳”的知识点。我刷题、带新人、准备面试这么久反复看到同一种情况状态定义想清楚了一写转移就超时或者小数据能过数据规模一大直接内存爆炸。这篇文章就是一篇dp复习与dp优化的实操总结目标很直接——先帮你把动态规划的基本功重新焊牢再帮你把几种最常用的优化手段讲透包括滚动数组、状态压缩、前缀和优化、单调队列优化、斜率优化、四边形不等式优化和分治dp优化。适合三类人看正在系统复习dp准备算法竞赛的人、面试前临时抱佛脚想快速把背包和区间dp捡起来的人以及做工程时状态多到内存放不下、转移慢到跑不动的开发同学。全文不会有玄学所有优化方法都配有可运行的示例和复杂度对比。顺便说一句dp这个缩写在不同的领域代表完全不同的东西一些人谈dp第一反应是“数据并行”比如大模型训练里的PP、TP、DP分法但在这篇文章里dp就是动态规划是算法里那个用子问题答案拼出大问题答案的经典思想。如果看标题点进来是为了找数据并行那这篇不对路请绕道如果你要找的是算法里的动态规划优化那往下看保证有收获。1. dp复习先把状态、转移、边界这三件事做扎实1.1 为什么说“状态定义决定复杂度上限”动态规划的基础框架其实只有三句话定义状态、写出转移、确定边界。任何dp题都逃不开这三件事而99%的dp问题做不出来不是转移公式不会推而是状态定义从一开始就歪了。状态定义决定了整个算法的复杂度上限。同样一个问题用一维状态还是二维状态决定了空间是O(n)还是O(n^2)转移是O(1)还是O(n)。这一步定错了后面再优化的空间都很有限。所以复习dp我习惯先让大家反复练“把问题翻译成状态”这个动作你关心什么维度就保留什么维度你不关心什么维度就千万别往状态里塞。举个最典型的例子0/1背包。物品数量和背包容量是两个天然维度状态定义就是dp[i][j]表示前i个物品在容量j下的最大价值。这个定义一出转移几乎写死第i个物品要么不选继承dp[i-1][j]要么选从dp[i-1][j-w[i]]加上价值v[i]推过来。很多人觉得背包简单但就是这种基础模型里藏着dp优化的全部起点——因为二维数组明显有空间冗余因为一维转移明显可以省掉一重枚举后面的滚动数组优化其实都是在“压”这个定义。1.2 用0/1背包和区间dp重建手感和套路复习dp我最推荐的路径是先把线性模型打通再把区间模型打通。线性模型指的是背包、LIS、LCS这一类特征是状态天然沿着数组下标推进转移只依赖前面的位置区间模型指的是石子合并、矩阵链乘这一类特征是状态是区间[l, r]转移要枚举中间分割点。两类模型覆盖了dp入门到进阶的大部分场景。以区间dp最经典的“石子合并”为例。有n堆石子排成一排每次只能合并相邻两堆合并代价是两堆重量之和问把所有石子合并成一堆的最小总代价。状态定义是dp[l][r]表示合并区间[l, r]的最小代价转移是枚举一个分割点kdp[l][r] min(dp[l][k] dp[k1][r]) sum(l, r)这里sum(l, r)是区间重量和用前缀和O(1)算。如果暴力枚举k复杂度是O(n^3)。n200的时候能跑n2000直接爆炸。这个题就是四边形不等式优化最经典的靶子后面我会用一整节专门讲。新手写区间dp最容易错的是遍历顺序。很多人习惯直接枚举l和r结果发现用到的子区间还没算过。正确做法是先枚举区间长度len再枚举左端点l右端点r l len - 1。记住这个顺序问题后面会省很多调试时间。注意dp复习阶段最重要的不是背题而是建立一个自查清单——状态定义是否覆盖了所有决策维度转移是否覆盖了所有可能边界值是否会导致数组越界这三条检查完再谈优化。2. 空间维度的优化滚动数组与状态压缩2.1 滚动数组一维数组解决0/1背包的流程与逆序原因先说滚动数组。它的思想特别朴素如果dp转移只用到了上一层的状态那就不需要保留所有层开两个数组轮换就行。空间从O(n^2)降到O(n)这是性价比最高的一种dp优化几乎零成本、零风险。0/1背包的滚动数组是关键中的关键因为它是“逆序更新”的典型。为什么必须逆序因为一维数组在更新dp[j]时dp[j - w[i]]如果已经被本轮更新过就等于把同一个物品装了两次这就不再是0/1背包了。逆序遍历能保证dp[j - w[i]]还是上一轮的值这样每个物品最多被选一次。下面这段代码是最标准的写法// 0/1背包一维滚动数组 vectorint dp(C 1, 0); for (int i 1; i N; i) { for (int j C; j w[i]; j--) { // 注意逆序 dp[j] max(dp[j], dp[j - w[i]] v[i]); } }而完全背包恰恰相反每个物品可以选无限次那就要正序遍历让dp[j - w[i]]能被本轮结果覆盖这样才能实现“同一个物品可以反复取”。很多新手在这里搞混一遍遍wa还不知道错在哪。我的经验是写滚动数组背包前先在注释里标明“0/1逆序、完全正序”六个字这是最容易记住也最容易忽视的细节。2.2 状态压缩dp用整数表示集合以存储换时间状态压缩是另一类空间与时间的双重优化典型场景是集合类问题比如旅行商问题。n个城市每个城市去没去过是一个0/1集合信息。如果把“去过哪些城市”直接用数组维度表示那需要2^n个状态这在n 20时是可行的因为用整数位表示集合能大幅压缩存储和转移成本。以旅行商问题为例状态定义是dp[S][i]S是整数二进制第k位表示城市k是否已访问i表示当前在哪个城市。转移枚举下一个没访问的城市jdp[S | (1 j)][j] min(dp[S | (1 j)][j], dp[S][i] dist[i][j])这种写法的核心价值是“以空间换时间”2^n个状态每个状态转移O(n)总复杂度O(n^2 * 2^n)。n15以下随便跑n20时12亿次左右会吃力n25以上就不太可行了。实际工程中这种优化常见于路径规划、资源分配等离散组合场景。状态压缩dp有三个坑第一个是位运算优先级很多人写 S | (1 j) 时忘了加括号优先级错了直接出bug第二个是数组大小2^n * n在n较大时内存爆炸开数组前一定要算清楚第三个是初始状态比如TSP的起点是dp[1][0] 0剩下全是无穷大漏了初始化会让答案变成0或者负数。3. 转移阶段的加速前缀和、单调队列与二进制优化3.1 前缀和优化把O(n)的枚举变成O(1)查询dp优化的第二个方向是优化转移也就是让“从哪些状态转移过来”这个枚举过程变快。最常见、最容易上手的就是前缀和优化。适用场景很典型转移公式里要对一段连续区间的dp值求和或求最值而且这个区间端点随i单调变化。举个例子一维dp要计算某个前缀和dp[i] max(dp[i-1], dp[i-2] a[i])这里其实不需要优化因为只依赖前两个。但如果是下面这种转移dp[i] max( sum(dp[j]) for j in [i-k, i-1] ) cost[i]每一轮都重新遍历区间复杂度是O(nk)。如果k很大直接用前缀和或滑动窗口就能把求和部分降到O(1)。前缀和适合求和滑动窗口适合维护区间最值本质都是“把重复计算过的信息存下来”。我见过很多人在自己写的dp里明明有一段区间和是重复计算的却每次都去循环累加完全没有意识到可以预处理前缀和。这里给一个通用经验任何dp转移里出现“对j循环求和”的痕迹第一步就看看这个和能不能用前缀和表示出现“对j循环取max/min”的痕迹第一步就想想这个最值能不能用单调队列维护。3.2 单调队列优化滑动窗口与一类定长转移单调队列优化的本质是维护一个区间内的最值候选集合并且保证候选集合里的值按某种单调性排列。最典型的场景是滑动窗口最大值。dp转移里如果出现“长度不超过k的连续段的最优值”而且i从小到大推进、窗口也在推进那单调队列就能把每个状态的转移从O(k)降到O(1)。一个常见的dp模型是dp[i] max(dp[j] val(j))其中j在区间[i-k, i-1]内。如果val(j)只和j有关那么每个j进入窗口时就可以比较它与队尾元素在“未来”的优劣把永远不可能成为最优的旧元素出队。队列里存的是候选下标窗口滑动时先弹出过期下标再维护单调性最后队头就是当前最优。我写单调队列优化时有三个习惯第一队列里存下标而不是存值因为要用下标判断是否过期第二先“出队过期元素”再“入队新元素”顺序不能乱第三写完后用一个几十个数据的小样例人工推导一遍因为这类题一旦窗口边界算错基本只能靠对拍发现。这个优化在实际做题中极其常用尤其是滑动窗口类问题、多重背包优化、以及一些二维dp的降维转移里。3.3 多重背包的二进制拆分多重背包是背包家族里最容易出问题的成员。它有n种物品每种有数量s[i]个直接按0/1背包展开成每个物品跑一遍复杂度是O(N * C * s_max)遇到s很大的数据会直接超时。二进制拆分的思路很经典把s[i]分成若干个2的幂次和一个余数的组合比如13拆成1、2、4、6这四个数通过组合能表示1到13的所有整数。然后用拆出来的这些“新物品”跑0/1背包就能覆盖原问题的所有选取数量。复杂度从O(NCs)降到O(NClog s)。这种优化本质上是一种“等价变换”把指数级的组合空间压缩成了对数个基础物品。类似的思路也出现在快速幂和稀疏表里都是利用二进制表示来减少冗余。写过几道多重背包变体题之后你会慢慢形成这种直觉看到“有数量限制的选择问题”先想能不能用二进制的角度做等价拆分。4. 决策优化斜率优化与四边形不等式4.1 斜率优化从暴力枚举到凸包查询斜率优化是整个dp优化里概念最难、但一旦掌握收益极大的一类。它适用于一类特殊转移——决策之间存在“比值关系”可以把转移方程转化成直线求截距的问题。比如很多一维dp转移长这样dp[i] min( dp[j] (sum[i] - sum[j])^2 C )直接枚举j是O(n^2)n到10万就卡死。把式子拆开dp[i] min( dp[j] sum[j]^2 - 2*sum[i]*sum[j] ) sum[i]^2 C把sum[j]看作x坐标把dp[j] sum[j]^2看作y坐标把-2*sum[i]看作斜率k问题就变成了在所有已处理的点上找一条斜率为k的直线使其截距最小。如果这些点形成了凸包结构最优决策点会在凸包上移动于是可以用单调队列维护一个凸壳每个状态O(1)转移。斜率优化最难的地方不是公式推导而是理解“为什么能用凸包”。我的经验是用几何直觉去记忆。把每个j的二元组画在坐标系上然后想象一条斜率固定的线从下面往上推最先碰到的点就是最优决策。一旦这个画面在脑子里成立了代码只是几何过程的翻译。写斜率优化时有个比较麻烦的细节判断斜率时要避免除法带来的浮点误差。标准做法是把比较两个点斜率的过程转成叉积形式也就是移项后用long long相乘来比较。这里贴一段常见写法// 斜率优化维护下凸包求最小值 long long Y(int j) { return dp[j] sum[j] * sum[j]; } long long X(int j) { return sum[j]; } long long K(int i) { return 2 * sum[i]; } bool check(int a, int b, int c) { // (Y(b)-Y(a))/(X(b)-X(a)) (Y(c)-Y(b))/(X(c)-X(b)) // 转为乘法避免浮点 return (Y(b) - Y(a)) * (X(c) - X(b)) (Y(c) - Y(b)) * (X(b) - X(a)); }这种基于叉积的写法在竞赛里是标配在工程里也建议沿用因为浮点误差在数据量大时真的会让人排查到怀疑人生。斜率优化适用的题目特征非常明显转移方程里有二次项或者转移代价与两者的乘积有关出现这类项时就要警惕这题多半是斜率优化的靶子。4.2 四边形不等式区间dp的经典加速四边形不等式优化是区间dp爱好者的福音。它解决的核心问题是对于形如 dp[l][r] min(dp[l][k] dp[k1][r]) cost(l, r) 的转移如果满足“四边形不等式”和“单调性”两个条件那么最优分割点k会随着区间移动而单调移动于是可以在枚举k时收窄范围。以石子合并为例如果直接枚举所有k复杂度O(n^3)。优化后每次枚举k的范围从[l, r-1]缩成[opt[l][r-1], opt[l1][r]]其中opt记录每个区间的最优分割点。这个收窄看起来不多但总复杂度能摊还降到O(n^2)这在大数据量下是质的提升。判断一个题能不能用四边形不等式的标准我总结为三步第一步用暴力程序跑小数据把每个区间的opt值打出来第二步肉眼检查opt数组是否满足“对同一个左端点opt随右端点单调不减对同一个右端点opt随左端点单调不减”第三步如果单调性成立再用四边形不等式的理论条件验证或者直接优化后用对拍确认。实际做题中很多时候题目不会明确告诉你“满足四边形不等式”需要靠打表观察这也是这类优化不太为人熟知的原因。4.3 分治dp优化与决策单调性验证分治dp优化是另一种利用决策单调性的手段适用于dp[i][j] min(dp[i-1][k] cost(k1, j)) 这类分层转移问题也就是常说的“分治优化dp”。它的核心思想是如果每一层的决策点具有单调性那么计算这一层的所有dp值时可以用分治的方式每次先算中点的最优决策再确定左右两半的可选决策区间递归处理。复杂度从O(n^2m)降到O(nm*log n)。分治dp优化和四边形不等式优化是“同源不同术”四边形不等式通过记录opt来收窄枚举范围分治dp通过在决策值域上分治来减少枚举量。使用分治dp的前提还是决策单调性。很多人在做这类题时忽略了一个前置验证步骤先写一个暴力版本取几组随机数据验证决策点确实单调再上分治优化。这一步虽然额外耗时但能避免你在一道不符合单调性的题上浪费整晚。我个人的经验是决策单调性是所有决策类优化的“准入证”。没有单调性斜率优化、四边形不等式、分治dp全都不能用强行用会得到错误答案。所以无论哪种优化动手前先验证单调性是我反复强调的准则。5. dp优化选型速查与避坑实操5.1 优化方法选择速查表把前面几节的内容汇总成一张速查表方便在实际做题或工程中快速定位该用哪种优化。优化类型适用场景典型问题复杂度收益实现难度滚动数组转移只依赖前一层0/1背包、LCSO(n^2)到O(n)低状态压缩dp集合选择类问题TSP、子集划分空间大幅压缩中前缀和优化转移中出现区间求和划分型dpO(n)到O(1)低单调队列优化转移中取定长窗口最值滑动窗口、多重背包O(nk)到O(n)中二进制优化多重背包类数量选择多重背包O(ncs)到O(nclog s)低斜率优化转移含乘积/二次项任务安排、划分数组O(n^2)到O(n)高四边形不等式区间dp最优分割点单调石子合并O(n^3)到O(n^2)中分治dp优化分层转移且决策单调邮局问题、区间划分O(n^2m)到O(nm*log n)高这张表是我自己写题时反复用的自查清单。看到一道dp题先判断它的瓶颈在空间还是时间空间不够用滚动或状态压缩时间不够就按转移公式的特征去匹配优化手段。匹配的优先级是先看有没有重复计算的区间和或最值再看有没有乘积项或决策点单调性最后再决定上不上高级优化。5.2 调试dp的三种手段对拍、打表、样例走查dp题调试起来比普通题痛苦因为状态空间大、转移分支多错误往往藏在某个状态的边界条件里。这里分享三个我长期使用的调试手段。第一个手段是对拍。写一个暴力版本比如直接递归加记忆化再写一个优化版本用随机小数据反复比较两者输出。对拍能覆盖你没想到的边界分支。实现方式很简单生成随机数组暴力跑一遍优化跑一遍对比结果不同就停下来手动分析。第二个手段是打表。把dp数组在关键转移点的值打出来看尤其是中间状态的输出。比如滚动数组优化后把每轮更新后的dp数组打印出来人工对照转移方程推一遍很多问题立刻能发现——到底是数组越界了、顺序错了还是初始值不对一眼就清楚。第三个手段是样例走查。找一个最小的能复现问题的数据比如n3、容量为5的背包然后手动在纸上跑一遍你设计的转移流程。这个方法虽然“古老”但定位问题极其高效尤其是区间dp的遍历顺序问题纸上走一遍比盯屏幕半小时好使。5.3 常见问题与排查记录当我停止刷题、开始带别人写dp优化时发现新手容易踩的坑高度集中。我把它们整理成一份排查记录这几条每一条都是我亲眼见过的真实事故。数组维度混乱是最常见的问题。滚动数组优化把一个二维状态压成一维后很多人就分不清当前值是“本层”的还是“上一层”的。我建议在代码注释里明确标记“哪个循环代表层数哪个循环代表容量”同时每一轮更新前把数组打印出来确认一遍直到手感形成。遍历顺序错误是背包类问题的重灾区。0/1背包必须逆序完全背包必须正序这是两个完全相反的规则混一次就错一次。我自己的习惯是每写一个背包题都会先写两行注释这是0/1背包j循环逆序这是完全背包j循环正序。这两个注释帮我避免了无数次无谓的调试。边界索引错误在区间dp里出现频率极高。区间[l, r]中r l len - 1很多人直接把r写成l len导致数组越界。还有枚举k的时候k的范围是[l, r-1]但有人写成[l, r]重复计算了空区间。排查这类问题时我最常用的手段是在转移处加一条assert保证下标合法跑一遍数据就能精准定位。还有一类问题是“没用long long”。dp优化后计算量变大中间乘积很容易超过int范围斜率优化里尤其明显。凡是涉及乘法、累加的状态转移建议直接用long long代价只是很小的内存增加却能避免大量溢出bug。最后一个问题是“优化方案没有先用暴力验证正确性就上线”。很多人拿到一道符合四边形不等式特征的题二话不说就直接写优化版写完发现wa了但又不知道是优化写错了还是这题根本不满足优化条件。我的建议永远是先用记忆化暴力版本跑通小数据确认状态和转移都正确然后再上优化如果优化版有bug用暴力版对拍定位而不是对着代码苦想。末尾再分享一点个人经验动态规划优化这条路我走过不少弯路。最开始学斜率优化时我对着公式抄了三天代码抄到能默写但其实根本没懂为什么一条直线往凸包上碰就能决定最优决策。后来静下心画图、用几十组数据手动模拟那个“砰”的点扎进凸包里的瞬间我才真正觉得通了。所以我想说dp优化不是背诵模板它的每个优化手段背后都对应一种对问题结构的观察——滚动数组看到了依赖的局部性单调队列看到了窗口的滑动性斜率优化看到了决策的几何性四边形不等式看到了分割点的单调性。如果你现在卡在某道dp优化题上我的建议很简单写暴力、验证单调性、画图、对拍这四步做完大部分疑惑都能解开。优化技巧本身是有限的但问题结构千变万化真正值钱的是你判断“该用什么优化、为什么可以优化”的能力。这个能力只能靠大量动手积累没有捷径。最后再提一个小技巧准备一个dp优化选题本每遇到一种新优化就记一道代表题标清楚“问题特征”、“优化原理”、“复杂度变化”和“易错点”。等积累到三四十道题之后你会发现自己看到新题的第一眼就能大致判断出该用什么套路那种感觉很上瘾。这也是我从一个见到dp就头疼的初学者慢慢变成一个“遇题先想优化”的老手的过程。
