企业官网建设流程全解析

动态规划（dp）这个内容，我在前面几讲把基础框架搭完之后，很多同学还是会反馈同一个问题：单独看每一道题都能听懂，但自己拿到新题就发蒙，不知道到底该用背包、区间、树形还是别的什么变体。所以这一讲我就把常见的 dp 类型集中串一遍，当作一份“题型检索表”来用。每种类型我都会讲清楚它解决什么问题、状态怎么开、转移长什么样、有哪些容易踩的坑，尽量用能直接抄的模板和实战经验说话。

再说一句防止跑偏的话：现在去网上搜“dp”，出来的东西很杂，分布部署里面有 --dp 参数，显示器也有 DP 接口。咱们这里聊的 dp 永远只指动态规划（dynamic programming），后面不再重复解释。这篇文章适合已经会写一些简单递推、但还没形成系统题型意识的人，也适合刷题刷到瓶颈、想回头整理一遍 dp 框架的人。建议你读的时候手边放一张草稿纸，把每个案例的状态转移图自己画一遍，光看不画是记不牢的。

1. 动态规划底层逻辑：先把“建模”这件事想明白

很多人总以为 dp 的核心是状态转移方程，其实不是。状态转移方程只是把建模结果写出来，真正难的、也是决定成败的，是如何把一个实际问题抽象成状态、阶段、决策三个要素。如果这一步错了，后面代码写得再漂亮都是白搭。

1.1 状态不是猜出来的，而是用约束条件逼出来的

拿到一个 dp 题，我建议你先回答三个问题：这个题目从前往后推进时，哪几个关键信息会改变后续的选择？这些关键信息的取值有多少种？如果把这些关键信息组合起来当作一个“坐标”，一组坐标就对应一个子问题。

比如 01 背包，最朴素的状态是dp[i][j]，表示“考虑前 i 件物品，背包容量还剩 j 时能获得的最大价值”。为什么会有这两维？因为每件物品选或不选会影响剩余容量，而剩余容量又影响后续物品能不能装，所以物品编号和当前容量都是不可丢的信息。算法题里有一句话很到位：状态里必须包含所有影响“未来决策”的信息。如果发现某一步转移之后，之前做过什么会影响现在的结果，那说明你丢掉了一个必要维度。

还有一种常见误解是觉得状态开得越多越好。维度多确实信息全，但复杂度也会跟着爆炸。所以建模时要在“必要信息”和“可计算规模”之间做取舍。我见过不少人拿到树形题动不动就开三维数组，结果转移根本捋不清楚；也见过有人为了省一维空间强行压缩状态，最后把后效性也压进去了。个人经验是，先开一个维度清晰、不担心超内存的状态去验证正确性，跑通了再去优化空间，别一上来就挑战最精简写法。

1.2 KMP 算不算 dp？先学会区分“递推”和“动态规划”

有同学把热搜词里“kmp 算法属于动态规划吗”翻出来问我。这个问题挺有意思，能看出你对 dp 本质有没有理解。KMP 的 next 数组确实是按某种顺序递推出来的，也利用了之前匹配的信息，但动态规划更强调的是“分阶段做最优决策”和“子问题最优解推导全局最优解”。KMP 的 next 数组更多是一种精心设计的递推匹配关系，它没有“选 or 不选”“取最大/最小”这类决策过程，所以竞赛圈里通常不把它归到动态规划。你可以说它带有 dp 的影子，但不能把它当成典型的 dp 题去套模板。

这个例子正好说明了一件事：递推是 dp 的底层工具，但不是所有递推都是 dp。动态规划建模时必须有一个明确的“决策”，并且这个决策要让子问题从一个小规模状态推向更大规模状态。如果你看一道题只找到了递推关系，却没找到状态里有什么可优化的目标函数，那就要警惕，它可能只是一道数学递推或模拟题，硬套 dp 反而会把简单问题搞复杂。

1.3 无后效性和最优子结构，为什么是两条铁律

dp 能被使用，依赖两个前提：无后效性和最优子结构。无后效性说的是，当前状态一旦确定，之后怎么发展就只跟当前状态有关，不再关心以前是怎么走到这里来的。最优子结构说的是，大问题的最优解能从子问题的最优解拼出来。

很多初学者会把这两个概念背得滚瓜烂熟，但实际做题时总是忘了验证。比如最长上升子序列，如果你用dp[i]表示以第 i 个元素结尾的 LIS 长度，那转移时只要看前面哪些元素值更小，不需要知道那些更小元素的内部排列，这就是无后效性。如果你反过来设计成dp[i]表示前 i 个元素的 LIS，那转移就会非常别扭，因为你不知道上一个接在后面的元素是谁。

一个很实用的检查办法是：在纸上把状态转移图里随机挑两个不同路径，看它们能不能汇合到同一个状态，汇合之后继续往下走的结果是不是也一样。如果两个不同历史到达同一个状态后，未来选择不一样，就说明状态里漏信息了，后效性已经出现。处理办法通常不是去修改转移，而是想办法把缺失的那个“记忆”加进状态里，或者换一种扫描顺序让历史不再影响未来。

2. 背包 DP：从 01 背包到多重变体一次打通

背包问题可能是 dp 里最庞大也最像“套路集合”的一类，但它同时也是训练状态设计和滚动数组压缩的最佳入门题。很多看起来和背包八竿子打不着的题目，最后都能化成背包模型，所以把背包吃透，后面能省不少事。

2.1 01 背包为什么必须倒着枚举容量

01 背包的状态是dp[i][j]表示前 i 件物品放入容量为 j 的背包能得到的最大价值，常规转移是：

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);

压缩掉第一维之后，代码通常是：

for (int i = 1; i <= n; i++) { for (int j = m; j >= w[i]; j--) { f[j] = max(f[j], f[j - w[i]] + v[i]); } }

这里最核心的问题就是：为什么内层容量要倒着枚举？因为压缩后f[j]本质上表示上一轮“还没处理第 i 件物品”时的结果。如果正着枚举容量，比如先更新了f[3]，等枚举到f[5]时再去读f[3]，读到的已经是本轮加入过第 i 件物品之后的状态了，这就等于允许同一件物品连续放多次，01 背包就悄悄退化成了完全背包。

你可以用一个生活化的类比来记：正序更新相当于一个购物车里同一件商品能反复扫码，倒序更新才保证每件商品最多被拿一次。这个知识点看上去很简单，但实际考场上很多人写着写着就把循环方向写反了。我的自查习惯是：写完背包代码后立刻问自己一句“每件物品能拿几次”，如果只能拿一次，内层必倒序；如果能拿无限次，内层必正序。

2.2 完全背包、多重背包和分组背包的异同

完全背包跟 01 背包的唯一代码差别就是把内层循环改成正序，因为每件物品可以选任意多次。这个改法看似微小，但它背后的逻辑是：正序枚举时，f[j - w[i]]可能是已经包含当前物品的最优值，正好实现了“可以再放一次”的效果。如果你愿意，完全背包还能写成数学形式，不过实战中直接正序滚动即可，没必要绕远路。

多重背包是每件物品最多选有限次。暴力做法是把每件物品拆成num[i]个 01 物品，但数量大了会超时。标准优化是二进制拆分，把数量c拆成若干个“打包物品”，每个包由 1、2、4、8……件原物品组成，最后剩余的单独成一包。比如数量 13，拆成 1、2、4、6 四个包，这四个包的不同组合能表示 0 到 13 的任意取件数。为什么最后一包是 6 不是 8？因为 1+2+4+8 已经等于 15，超过 13，所以要把 13-1-2-4=6 作为剩余项。这样能把一次多重背包降成 O(n log c) 个 01 背包处理。

分组背包则是在容量约束之外，还要求每组最多只能选一个物品。常见做法是把“组”作为外层阶段，组内每个物品作为候选，在容量循环里做 01 背包式转移，只是不能同时选两个同组物品。做分组背包最容易错的地方在于：必须先把组内所有物品都根据同一个旧状态更新完，再进入下一组，否则容易出现组内互相影响，导致一组选了两个。

2.3 把可变代价物品重新理解成“二维费用”和“依赖背包”

当题目里出现“既要付出容量，又要付出重量”时，就变成二维费用背包，常见写法是在原状态上再加一维，比如dp[k][j]表示容量为 k、承重为 j 时的最大价值。如果其中一个费用维度特别大，还要考虑逆序滚动或把某个费用改成价值再做转化。

依赖背包最典型的例子是“主件与附件”问题，比如必须买了主件才能买附件。这类题目通常先把同一主件下的所有附件选择方案枚举出来，生成若干个分组选项，再按分组背包处理。严格说，树形结构更复杂的依赖关系就要用树形 dp 来合并子树，这一块后面我会单独讲。总之，背包问题的灵魂是“面对同一个资源，怎么分配才最优”，只要看出一道题本质是在做资源分配，就可以试着往背包模型上靠。

3. 区间 DP：先想“最后一步合并”，再想区间从哪里切开

区间 dp 不像背包那样把“前 i 个”当阶段，而是把“某个连续区间”作为状态。它处理的场景往往是一个序列或环上，需要把左右两部分的答案合并起来，而合并点会影响总代价。

3.1 为什么区间 dp 的枚举顺序是“先长度，后左端点”

以经典的石子合并为例：有 n 堆石子排成一排，每次只能合并相邻两堆，合并代价是两堆石子数之和，问最终合并成一堆的最小总代价。如果设f[l][r]表示把第 l 堆到第 r 堆合并成一堆的最小代价，那最后一步一定是某个 k 位置把左右两边各合并成一堆，再合并这两个大堆，所以转移是：

f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + sum[r] - sum[l - 1]);

这里的sum[r]-sum[l-1]是合并最后两堆那一下的代价，也就是区间内所有石子的总数。要计算f[l][r]，你必须保证所有更短的区间已经算出来了，所以枚举顺序一定是以区间长度为外层循环，从 2 开始逐渐增加到 n，然后再枚举左端点 l，由长度推出右端点r = l + len - 1。如果你用左端点作为外层循环，很多状态会依赖还没计算出来的更长或更短的组合，代码就会出错。

还有一个小技巧：有些区间 dp 的过程不好用递推方向想清楚，可以干脆写记忆化搜索。在记忆化版本里，dfs(l, r)递归处理，天然只依赖更小区间，正确性比手推三重循环更容易保证。递推代码跑得快，搜索代码更不容易写错，两者没有谁绝对更好，关键是你会用哪个。

3.2 环上问题：复制一倍数组就解决了

很多区间 dp 题目不是给你一排石子，而是给你一个环。比如洛谷的环形石子合并，每次合并哪两堆都可以。这时如果直接在环上枚举的话，合并点没有固定起点，状态会非常难写。通用的套路是把原数组复制一份接到自己后面，形成长度 2n 的数组，然后在这个线性数组上做普通区间 dp，最后对所有长度为 n 的区间取答案。

这个技巧的原理很简单：环的切开位置，一定对应原数组某个位置，复制成 2n 长度之后，每一种“从某个起点连续取 n 个元素”的选择都覆盖了环上所有情况。这样你不需要真的去切环，只需要枚举长度为 n 的窗口就行。复杂度会多一个常数，但对绝大多数题目完全能接受。

3.3 几种看起来不像区间 dp 的题型

区间 dp 不只是“合并石子”的形态。比较常见的是括号匹配：给你一个括号序列，问最少插入多少个括号能让它合法。这种题的状态也是f[l][r]，转移会分成两类：如果s[l]和s[r]能配对，可以先考虑f[l+1][r-1]；此外还要枚举 k，把区间拆成两段分别处理，因为括号合法序列可能由多个并列合法片段组成。

还有一种经典是凸多边形的最优三角剖分：把凸 n 边形用不相交的对角线分成若干个三角形，每个三角形有权值，求最小总权值和。因为剖分总会有一条边把多边形切成两个子多边形，所以状态和转移跟区间 dp 完全同构。判断一道题是不是区间 dp 其实有个很直觉的信号：题目给的是一段连续序列或环，并且你需要把区间分块、合并、配对、剖分，最终答案要覆盖整个区间。只要看到“连续一段”和“切分合并点”同时出现，就可以优先往区间 dp 方向想。

4. 状态压缩 DP：把集合状态塞进二进制

有一类 dp 的“状态”不是一个数字，而是一个集合。如果你真的把集合写进数组下标，那计算机可没法处理dp[{1,3,5}]这种东西。但如果集合里的元素总数 n 不算大，比如不超过 20，就可以用二进制整数的每一位表示某个元素在不在集合里。这个手法叫状态压缩，或者叫状压 dp。

4.1 什么时候该想到用状压

状压 dp 最典型的特征是：某个决策会改变一个“使用过的元素集合”，而且这个集合必须作为后续决策的依据。比如旅行商（TSP）问题：给 n 个城市之间的距离，从一个城市出发，每个城市恰好经过一次，最后回到出发点，问最短路径。如果只记录“当前在哪个城市”——也就是一维状态——你会不知道哪些城市已经去过了，可能重复经过；必须把“已经访问过的城市集合”也记下来。

所以需要状压的场景通常满足两个条件：一是集合元素个数很小，n 大约在 10 到 20 之间，2 的 n 次方作为数组大小还能接受；二是集合本身会参与转移，不记录就产生后效性。如果 n 到 25 以上，普通状压基本会超空间，这时就得考虑 meet-in-the-middle 或别的模型了。

4.2 从集合枚举到 TSP 的转移写法

TSP 的状态通常设成dp[mask][u]，表示当前已经访问过的城市集合是 mask，最后一个到达的是城市 u，当前已走的最短距离是多少。初始状态是dp[1][0] = 0，只有第 0 个城市已访问，并且当前就在 0。转移时枚举下一个还没去过的城市 v：

memset(dp, 0x3f, sizeof(dp)); dp[1][0] = 0; for (int mask = 1; mask < (1 << n); mask++) { for (int u = 0; u < n; u++) { if (!(mask & (1 << u))) continue; for (int v = 0; v < n; v++) { if (mask & (1 << v)) continue; int nmask = mask | (1 << v); dp[nmask][v] = min(dp[nmask][v], dp[mask][u] + dis[u][v]); } } }

最后从所有终点回到 0 取最小值，也就是遍历dp[(1<<n)-1][u] + dis[u][0]。这种写法的时间复杂度是 O(2^n * n^2)，空间复杂度是 O(2^n * n)。实测下来 n=16、17 很轻松，n=20 在多数竞赛题目里已经偏紧，需要看具体时限。如果你发现 n 在 15 以下，甚至可以不用那么刻意优化，直接暴力跑。

4.3 枚举集合子集时的复杂度陷阱

状压还有一种常见操作是“从当前集合的子集转移”，比如把一个大集合 S 拆成若干子集分别处理，这时候写成：

for (int sub = S; sub; sub = (sub - 1) & S) { dp[S] = min(dp[S], dp[sub] + dp[S ^ sub]); }

这行代码能枚举 S 的所有非空真子集。很多人以为对所有 S 枚举一遍子集的复杂度是 O(2^n * 2^n) = O(4^n)，其实不对。因为真实数量是对每个子集 S 枚举它的子集，总和是 3^n。你可以把每个元素看成这三种状态之一：不属于 S、属于 S 但不属于 sub、属于 sub。所以只要 n 不大，用这种思路是可行的，但 n 一旦到 20 以上，3^n 的增长会非常恐怖，必须另找优化。

状压题里的位运算技巧也很值得整理，比如用x & -x取最低位 1，用__builtin_ctz获得第几位，用(1 << n) - 1表示全集。写代码时我习惯先把位运算的语义写在注释里，比如“mask & (1 << u) 表示 u 在集合中”，因为这类代码一旦出错，调试起来比普通数组题难受很多。

5. 树形 DP：把普通 dp 搬到一个有父子关系的图上

树形 dp 从代码层面看就是深度优先搜索后序遍历时做 dp，但它的思维难点在于“孩子节点的返回值怎么合并成父节点的答案”。树这个结构天然适合分治，因为子树之间互不干扰，满足最优子结构的条件。

5.1 最经典的“选与不选”模型

入门题可以看“没有上司的舞会”：公司的员工关系形成一棵树，如果选了一个节点，它的直接子节点就不能选；每个节点有一个权值，问能选出的最大权值和。

设置dp[u][0]表示以 u 为根的子树中，u 不参加舞会时的最大快乐值；dp[u][1]表示 u 参加舞会时的最大快乐值。因为 u 不参加时，子节点可参加也可不参加，所以累加每个子节点的两种情况取最大值；u 参加时，子节点只能不参加：

void dfs(int u, int fa) { for (int v : g[u]) { if (v == fa) continue; dfs(v, u); dp[u][0] += max(dp[v][0], dp[v][1]); dp[u][1] += dp[v][0]; } dp[u][1] += val[u]; }

这个模型衍生出的题目非常多：树上最大独立集、树的最小点覆盖、监控摄像头问题等，核心都是同一套“选 or 不选”状态。只要发现一个决策会影响相邻节点，而且关系是树状，就先往这个方向想。

5.2 树形背包：把子树当作一个可选组

如果树上的每个节点也有“容量”或“个数”的限制，就可能需要把子树当作物品组来做背包。经典的“选课”问题是这样的：课程之间有先修关系，必须先修了父课程才能学子课程，每个课程有学分，问最多选 m 门课能获得多少学分。

设dp[u][j]表示在以 u 为根的子树中，选了包含 u 在内一共 j 门课能获得的最大学分。处理每个孩子 v 时，把 v 子树看作一组物品，可以分配给它 1 门、2 门……但不能超过总预算。合并子树的代码框架是：

void dfs(int u) { dp[u][1] = score[u]; sz[u] = 1; for (int v : g[u]) { dfs(v); for (int j = m; j >= 1; j--) { for (int k = 1; j + k <= m; k++) { dp[u][j + k] = max(dp[u][j + k], dp[u][j] + dp[v][k]); } } sz[u] += sz[v]; } }

这里为什么 j 要倒序？和背包里的滚动数组一个道理，它保证合并多个子树时，每个子树最多被使用一次。写这种题最容易踩的坑是忘记初始化：因为选 u 必须先占用一个名额，dp[u][1]必须提前赋值为 score[u]。如果你没有在进入孩子前初始化，后面合并时转移永远从 0 开始，结果会差出一个根节点的权值。

5.3 换根 DP：从“固定根”扩展到“每个点都当根”

有些树形 dp 不是只求一个固定根的答案，而是要求“以任意一个点为根时”的答案，比如求树上每个节点到其他所有节点的距离和，或者每个节点作为根时树的高度。如果对每个点都重新做一次 dfs，复杂度达到 O(n^2)，n 稍微大一点就超时。

换根 dp 的思路是两次扫描。第一次任选一个根，做自底向上的 dp，得到以这个根为参考的答案和每个子树的贡献。第二次从根出发做自顶向下，利用父节点已经算出的答案，通过“贡献调整”推导子节点作为根的答案。这个调整很像“把一条边从父到子的方向翻转之后，距离和怎么变化”：子树内的点距离减 1，子树外的点距离加 1，所以答案变化量可以用子树大小求出。换根题最考验人的地方不是第一次 dfs，而在于第二次维护“从父亲到儿子”的转移关系时必须想清楚：哪些信息是来自整个树，哪些只来自当前子树。

6. 数字 DP：把“很大范围内的计数”按位拆开

数字 dp 解决的问题一般是：统计区间 [L, R] 内有多少个整数满足某种条件，比如不含某个数字、相邻两位差不小于某个值、二进制表示里没有连续的两个 1。这类题的数字范围往往到 10^18，你不可能真正遍历每个数，只能按“数位”来做 dp。

6.1 为什么区间计数都可以转换成前缀差

数字 dp 的通用入口，是把“求 [L, R] 内满足条件的数量”变成solve(R) - solve(L - 1)，其中solve(x)表示统计 [0, x] 内有多少个满足条件的数。前缀和的思路在数位 dp 里特别关键，因为你只要写出一个能处理“上界 x”的函数，区间两端的值就都解决了。

接下来需要逐位填数字。每次填一个数位时，要判断当前位能不能取某个数字，取决于前面是否已经“贴着”上界。比如统计十进制数位时，x 是 345，高两位填了 3、4，那第三位最大只能取 5；如果前面已经填得比 x 小了，后面每一位都可以随便填 0 到 9。这个“是否贴住上界”的条件在递归里通常用limit表示。

6.2 记忆化搜索是最好写的数字 DP 模板

我强烈推荐用记忆化搜索来实现数位 dp，而不是硬写三重循环。因为递归函数的语义清晰，要加几个限制条件都很自然。这里给出一个二进制例子：统计 [0, n] 中二进制表示没有连续两个 1 的数的个数。

#include <bits/stdc++.h> using namespace std; int bit[40]; long long memo[40][2]; long long dfs(int pos, int last, bool limit) { if (pos < 0) return 1; if (!limit && memo[pos][last] != -1) return memo[pos][last]; int up = limit ? bit[pos] : 1; long long ans = 0; for (int d = 0; d <= up; d++) { if (last && d) continue; // 不能出现连续两个1 ans += dfs(pos - 1, d, limit && (d == up)); } if (!limit) memo[pos][last] = ans; return ans; } long long solve(int n) { int len = 0; while (n > 0) { bit[len++] = n & 1; n >>= 1; } if (len == 0) bit[len++] = 0; memset(memo, -1, sizeof(memo)); return dfs(len - 1, 0, true); }

为什么记忆化只在!limit时存储？因为当limit == true时，当前搜索被上界绑定了，它只对应一条具体的前缀路径，不能代表其他状态；而limit == false时，无论当前前缀是什么，后面可选的数位范围都一样，所以可以统一缓存。

6.3 前导零和边界条件是两个大坑

数字 dp 写的代码看起来短，但出错率极高，最常见的坑是前导零。比如统计十进制数里数字 0 出现的次数，你不能把数字 100 中高位的“空”也算成 0，否则会多出很多计数。处理办法是在 dfs 里多加一个lead参数，表示当前是否还在填前导零。当lead == true且当前位填 0 时，数字仍然没有真正开始，因此既不影响状态的特殊条件，也不能把它计为一次数字出现。

边界条件方面，solve(0)到底返回 1 还是 0，取决于题目是否把 0 当作合法数。如果你统计的是“自然数中满足条件的数”，通常 0 也算，那solve(0)返回 1；但你做区间减法时solve(L - 1)当 L=0 时需要特别小心，别让下标变成负数。另一个容易忘的点是数组长度，while (n > 0)会把 n 的二进制位存成从低位到高位，高位不足时需要补 0，不要漏掉最高位导致把 n 的最高位截掉。

7. DP 优化：从 O(n²) 往 O(n log n) 走的几个典型方法

dp 题做到一定量以后，你会发现很多题的状态设计和决策已经很清晰，但复杂度卡在 O(n²) 甚至 O(n³) 过不了。此时就要上优化，而优化的核心从来不是花哨技巧，而是“复用已经算过的中间结果”。

7.1 先判断复杂度瓶颈在哪一层

拿到一个复杂度过高的 dp 题，先不要急着背优化模板。你要把复杂度拆成“状态数”和“每个状态的转移复杂度”两部分。如果状态数本身是 O(n²)，那通常没法再压缩，这时候优化方向是让每次转移从 O(n) 变成 O(log n) 或 O(1)。如果状态数是 O(n)，转移是 O(n)，那就是经典的 1D/1D 动态规划，可以想办法用数据结构、单调队列或凸包维护候选值。

我见过太多人一看到题目就想套“斜率优化”，却没先搞清楚自己的开销来自哪里。比如区间 dp 的 O(n³) 复杂度，如果合并代价满足四边形不等式，可以用决策单调性优化到 O(n²)，但这跟斜率优化完全是两码事。先分析瓶颈是第几步，比急着写一个看似高级的优化重要得多。

7.2 决策单调性与分治 dp 优化

有一类 dp 转移长这样：dp[k][j] = min(dp[k-1][p] + w(p+1, j))，其中p < j，w 是某种区间代价函数。这类问题在做第 k 层时，如果第 k-1 层的值已经算完，且 w 满足一定条件，那么最优决策点会随着 j 的增大单调不降，也就是决策单调性。

判断一个代价函数是否满足四边形不等式并不容易，但竞赛里常用“打表验证”来试探。你先用朴素 dp 跑小数据，记录每个 j 的最优 p，如果 p 的序列单调不减，就可以考虑分治优化。实现思路是：用递归处理当前需要计算的 j 区间[l,r]，同时传入可能的决策点范围[optL, optR]。对中间的 mid，暴力枚举它可能的决策点，找到最优位置 pos，然后递归算左边、右边，并把决策点范围压成一半。核心伪代码如下：

void solve(int l, int r, int optL, int optR) { if (l > r) return; int mid = (l + r) >> 1; long long bestVal = INF; int bestPos = optL; for (int p = optL; p <= min(optR, mid - 1); p++) { long long val = dpPrev[p] + cost(p + 1, mid); if (val < bestVal) { bestVal = val; bestPos = p; } } dpNow[mid] = bestVal; solve(l, mid - 1, optL, bestPos); solve(mid + 1, r, bestPos, optR); }

这里的核心好处是：每次递归把区间一分为二，而每一层里所有枚举的 p 加起来不会跨过整个 opt 范围太多，整体复杂度从 O(n²) 降到 O(n log n)。需要注意，这个优化只在“外层阶段固定，内层 j 之间相互独立”时好用，如果你每个 dp 值还依赖同一层的其他 dp 值，那分治顺序就要重新设计。

7.3 单调队列优化和斜率优化什么时候用

单调队列优化解决的是另一类问题：状态转移里的候选 j 在一个滑动窗口内移动，并且窗口边界随 i 单调增加。最典型的例子是“从前面一段连续区间里取最大值来更新当前值”。这时你可以用一个双端队列维护候选值，保证队头是最优的，同时把过期选项从队头弹出。

斜率优化则用于把转移方程改写成直线求最值的形式，比如dp[i] = min(dp[j] + (sum[i] - sum[j])^2 + C)这类带平方项的式子，展开后变成若干条斜率和