算法设计第 10 章：算法优化——决策单调性、四边形不等式与剪枝

前九章在"设计"算法，这一章在"改造"算法：同一个正确算法，把 O(n³) 压到 O(n²)、把 O(n²) 压到 O(n log n)，靠的不是换思路，而是发现结构里被浪费的枚举。优化的通用套路只有一句：先找到瓶颈那一层循环，再证明这一层枚举的范围可以缩小。四种武器——决策单调性、四边形不等式、迭代加深、剪枝——都服从这条逻辑。

一、先定位瓶颈：复杂度花在哪一层

拿到一个 O(n³) 的 DP，先问三个问题：

1. 状态数是多少？（通常 O(n²)，区间 DP 的 i、j）
2. 每个状态的转移枚举了多少个候选？（通常 O(n)，断点 k）
3. 这个枚举里，有没有大量候选永远不可能成为最优？

第三问是全部优化的入口。矩阵连乘枚举 k ∈ [i, j)，石子合并枚举 k ∈ [i, j)，本质都是"在区间里找一个断点"。若能证明最优断点随区间移动而单调移动，枚举范围就能从 O(n) 缩到均摊 O(1)。

优化的收益必须用总代价 = 状态数 × 单次转移代价来核算，只优化一半（比如状态数降了但转移没降）往往白做。

二、分治优化与决策单调性

设 dp[i] = min_{j < i} { dp[j] + w(j, i) }，若最优决策点 opt[i] 满足

opt[1] ≤ opt[2] ≤ … ≤ opt[n]（决策单调性），

则可用分治优化：计算区间 [l, r] 的 dp 值时，已知其最优决策点落在 [optl, optr]；取中点 mid，暴力扫描 [optl, optr] 求出 opt[mid]，再递归计算 [l, mid−1]（决策范围 [optl, opt[mid]]）与 [mid+1, r]（决策范围 [opt[mid], optr]）。

复杂度分析：每层递归的扫描总长度是 O(n + 决策区间长度)，共 log n 层，总计 O(n log n)，比朴素的 O(n²) 少一个量级。

决策单调性的常见充分条件：代价函数 w 满足四边形不等式，或 w 具有"区间包含的单调性"（区间越大代价越大且增长不减速）。

若 opt 还满足更强的"每个 j 只在一段连续 i 上最优"，可以用单调队列 / 指针扫描做到 O(n)。

三、四边形不等式优化区间 DP

定义：对 a ≤ b ≤ c ≤ d，若

w(a, c) + w(b, d) ≤ w(a, d) + w(b, c)

则称 w 满足四边形不等式（交叉小于嵌套）。直观含义：两段区间"交错"的代价不大于"包含"的代价。

定理（Knuth 优化）：若 w 满足四边形不等式且 w 关于区间长度单调，则区间 DP

m[i][j] = min_{i ≤ k < j} { m[i][k] + m[k+1][j] } + w(i, j)

的最优断点满足

s[i][j−1] ≤ s[i][j] ≤ s[i+1][j]

于是 k 的枚举范围从 j−i 个缩到 s[i+1][j] − s[i][j−1] + 1 个。所有区间的枚举总量为 O(n²)（ telescopes 求和），总复杂度从 O(n³) 降到 O(n²)。

验证方法（石子合并为例）：w(i,j) = sum(i..j) 是区间和，显然满足四边形不等式（两边都是 sum(a..c)+sum(b..d) 与 sum(a..d)+sum(b..c)，交叉项被重复计入更多次，不等式成立），故可用 Knuth 优化。代价函数是"区间和""区间最大值"这类可加量时，几乎总能满足。

四、带权区间最短路优化实例

两类常见形态，优化手法完全不同：

其一，区间 DP 型（如"合并石头的最低成本""多边形三角剖分"）：转移是 m[i][j] = min_k { m[i][k] + m[k+1][j] + w(i,j) }，用上节的四边形不等式，O(n³) → O(n²)。

其二，区间连边最短路：图上有 n 个点排成一行，边是"从点 u 到区间 [l, r] 内任意点"，权为 w。朴素建图边数是 O(n²)，Dijkstra 变 O(n² log n)。用线段树优化建图：建两棵线段树（入树、出树），把"连向一个区间"拆成 O(log n) 个线段树结点，边数降到 O(n log n)，最短路总复杂度 O(n log² n)。

两者共同的思路：把"区间"这个对象本身建成结构（DP 表或线段树结点），让一次操作覆盖一整段，而不是逐个元素枚举。

五、迭代加深搜索与启发函数剪枝

迭代加深（IDDFS）：限制深度上限依次为 1, 2, 3, …，每轮做一次深度受限的 DFS，直到找到解。

• 空间 O(d)（只有一条路径），优于 BFS 的 O(b^d)。
• 时间 O(b^d)，重复搜索浅层只多一个常数因子（等比级数求和，(b^(d+1)−1)/(b−1)）。
• 适合解的深度未知、状态空间宽的问题。

IDA*：在 IDDFS 上加启发函数。设 g 为已走代价、h 为到目标的可采纳估计（不高估），f = g + h。每轮阈值取"上一轮所有超出阈值的最小 f"，只扩展 f ≤ 阈值 的结点。h 越紧，剪掉的越多；h ≡ 0 时退化为 IDDFS，h 精确时一步到位。

可采纳性是正确性的前提：h 一旦高估，最优解可能被剪掉。八数码常用"曼哈顿距离之和"作 h，它从不高估，且比"错位数"紧得多——同一个实例，错位数要扩几十万结点，曼哈顿距离只要几千。

六、对称性、可行性等高级剪枝

剪枝类型	依据	例子
可行性剪枝	当前部分解已违反硬约束	n 后同对角线、背包超容量
最优性剪枝	当前界已劣于已知最优	背包上界 ≤ bestp、TSP 下界 ≥ bestc
对称性剪枝	解的等价类只需搜一次	n 后第一行只试前 n/2 列；圆排列固定首元素
支配剪枝	一个分支严格劣于另一分支	相同物品去重、状态记忆化
顺序剪枝	先试约束最强的分支	着色按度数降序、背包按单位价值降序

对称性剪枝的收益常被低估：n 后问题固定第一行只搜前 n/2 列，搜索量直接减半；带重复元素的排列问题，排序后跳过"与前一个相同且前一个未使用"的分支，能把 n! 压到实际的多重集排列数。

记忆化是另一条路：把"已搜索过的状态"记下来，遇到直接返回。它把搜索树变成 DAG，是从回溯跨向动态规划的那一步。

易错点

1. 未验证决策单调性就直接套分治优化，得到错误答案（单调性必须证明，不能假设）。
2. 四边形不等式与"区间 DP 可优化"混为一谈，忽略 w 还需单调。
3. IDA* 的 h 高估，剪掉最优解。
4. 迭代加深误以为重复搜索让复杂度翻倍，实际只多常数因子。
5. 只降状态数不降转移代价，总复杂度没变。

这一章在整门课里的位置

本章是全课程的收口：分治优化来自第 2 章的递归式分析，四边形不等式是第 3 章 O(n³) 区间 DP 的直接优化，剪枝体系是第 5、6 章的自然延伸，IDA* 则是第 6 章优先队列分支限界在内存受限时的替代。五种策略的适用场景可以这样对照：

策略	适用条件	典型复杂度
分治	子问题独立、可合并	O(n log n)
动态规划	最优子结构 + 重叠子问题	O(n²)~O(n³)
贪心	贪心选择性质可证	O(n log n)
回溯 / 分支限界	解空间可剪枝	指数，实际远小
概率 / 近似	精确解不可行	多项式，有误差界

本文是《算法设计与分析（89 讲）》第 10 章的知识点摘要。完整板书与代码见 课程页；上一章 子串匹配。下一步建议看 数据结构与算法（93讲）。