SMAWK · O(m+n)

行最小值：Monge 与 SMAWK

Knuth 单调性：最优 BST 的根不回头的提速来自根位置的单调性：ComputeCostAndRoot 在一行候选里找最小代价，搜索区间被两侧的答案夹住。把最优 BST 的上下文剥掉，剩下的子问题在各种 DP 里反复出现：给一个 $m \times n$ 矩阵，求每一行最左的最小值落在哪一列。本页沿两档结构假设走两档复杂度：行最小值的位置单调时，分治做到 $O(m + n \log m)$ ；任取子阵仍单调时，SMAWK 做到 $O(m + n)$ 。

1 · 从 DP 内层到行最小值

行最小值问题（row minima）的输入是 $m \times n$ 矩阵 $M$ ，输出是每行最左的最小值位置 $LM(i)$ （并列时取最左）。不借助任何结构，只能逐行全扫：每行 $n - 1$ 次比较，合计 $m(n - 1)$ 次， ${5 \times 5}$ 矩阵是 20 次。

很多二维 DP 的内层循环就是这个形状。Erickson 在附录 D 里给的引例正是最优 BST：固定外层的区间长度 $d$ ，令 $M[i, r] = \mathit{OptCost}[i, r - 1] + \mathit{OptCost}[r + 1, i + d]$ （ $r$ 越界处取 $\infty$ ），ComputeCostAndRoot 求的就是这个 $M$ 第 $i$ 行的最小值 [2]。矩阵不必真的建出来，读到哪格才算哪格；这个观察在 §6 回收。

定义 1.1（monotone） 矩阵 $M$ 是 monotone 的，若 $LM(1) \le LM(2) \le \dots \le LM(m)$ ，即行号增大时最左最小值的位置不向左回头。

书中的 ${5 \times 5}$ monotone 样例（各行最小值加框）：

\begin{bmatrix} \boxed{12} & 21 & 38 & 76 & 27 \\ 74 & \boxed{14} & 14 & 29 & 60 \\ 21 & \boxed{8} & 25 & 10 & 71 \\ 68 & 45 & 29 & \boxed{15} & 76 \\ 97 & 8 & 12 & \boxed{2} & 6 \end{bmatrix}

行最小值位置依次是 $[1, 2, 2, 4, 4]$ ，非降。第 2 行有并列的 14、14， $LM$ 的口径取最左；这个细节在 §5 成为主角。

2 · monotone 矩阵上的分治

单调性让「先算中间行」立即生效：全扫第 $\lceil m/2 \rceil$ 行得到位置 $h$ ，上半部分的答案只会落在列 ${1 .. h}$ ，下半部分只会落在列 $h .. n$ ，两个子问题的列区间被夹住。每层递归的比较总量是 $O(n)$ ，递归树深 $\log_2 m$ 、结点 $O(m)$ 个，合计 $O(m + n \log m)$ 。

书中还给了一个等价的奇偶形式：先递归求出全部奇数行的 $LM$ ，偶数行 ${2i}$ 被 $LM(2i - 1) \le LM(2i) \le LM(2i + 1)$ 夹住，在这个小区间里全扫；全部偶数行的比较合计 $\sum_i \bigl( LM(2i + 1) - LM(2i - 1) \bigr) \le n$ 。两种写法访问同一批格子、做同样的两两比较，只是遍历序不同（一个深度优先，一个广度优先）。奇偶形式在 §4 回收：SMAWK 的递归骨架就是它。

实测对照用 §3 的 totally monotone 样例（同为 ${5 \times 5}$ ，行最小值位置同样是 $[1, 2, 2, 4, 4]$ ）：暴力 20 次比较，分治 10 次。小矩阵上省一半； $m = n$ 时渐近从 $O(n^2)$ 降到 $O(n \log n)$ 。

图 2-1 · 同一张 5×5 矩阵上的三种行最小值算法，绿色格为所选算法给出的各行最小，读数并列暴力、分治的比较数与 SMAWK 的 lookup 数。可切换书中两个预设或直接改写格子，徽标即时判定 monotone / totally monotone / Monge，虚线框标出首个违反处；所选算法的前提不成立时，结论条对照暴力结果给出裁决。

3 · totally monotone 与 Monge

定义 3.1（totally monotone） 矩阵 $M$ 是 totally monotone 的，若任取行子集与列子集（不必相邻）得到的子阵都是 monotone；等价地，每个 ${2 \times 2}$ 子阵都是 monotone，即不存在「上行最小在右、下行最小在左」的四个格子。

§1 的样例过不了这一关。违反处不止一处：书中标灰的是行 $\{1, 3\}$ 与列 $\{3, 5\}$ 交出的子阵（上行 38、27，下行 25、71——上行最小在右，下行最小在左）；本页判定器按行序扫描，先撞见的是行 $\{1, 2\}$ 与列 $\{3, 5\}$ 。书中把几个格子改掉（27 抬到 89、74 降到 47、25 降到 20、45 降到 16），得到 totally monotone 的版本：

\begin{bmatrix} \boxed{12} & 21 & 38 & 76 & 89 \\ 47 & \boxed{14} & 14 & 29 & 60 \\ 21 & \boxed{8} & 20 & 10 & 71 \\ 68 & 16 & 29 & \boxed{15} & 76 \\ 97 & 8 & 12 & \boxed{2} & 6 \end{bmatrix}

totally monotone 的直接验证很贵：逐一检查全部 ${2 \times 2}$ 子阵要 $O(m^2 n^2)$ 。实务上更常见的入口是一个更强也更好查的性质。

定义 3.2（Monge 矩阵） $M$ 是 Monge 的，若对所有 $i < i'$ 、 $j < j'$ 有 $M[i, j] + M[i', j'] \le M[i, j'] + M[i', j]$ 。这条不等式也叫四边形不等式（quadrangle inequality）。

引理 3.3 Monge 矩阵都是 totally monotone。

证明逆否。若 $M$ 不 totally monotone，则存在 $i < i'$ 、 $j < j'$ 使 $M[i, j] > M[i, j']$ 且 $M[i', j] \le M[i', j']$ ，两式相加得 $M[i, j] + M[i', j'] > M[i, j'] + M[i', j]$ ，违反四边形不等式。∎

Monge 好查得多：不等式只需对相邻行对与相邻列对验证（相邻全成立可归纳出一般情形），isMonge 扫一遍 $O(mn)$ 。它也好构造：两条平行线上各排一列点，点对的欧氏距离矩阵由三角不等式保证 Monge；行常量、列常量矩阵以及任意 Monge 矩阵的非负组合仍是 Monge。DP 里常见的来源是几何距离与凸代价，落地：SMAWK 加速一维分段 DP 的代价矩阵属于后者。

两条包含关系都是真包含。monotone 样例不 totally monotone 已见上文；而书中的 totally monotone 样例喂给 isMonge，在第 1–2 行与第 4–5 列的相邻 ${2 \times 2}$ 上报出违反： ${76 + 60 = 136 > 89 + 29 = 118}$ 。书里没有点破这一层，是把样例交给判定器时撞见的：Monge 蕴含 totally monotone，反向并不成立，SMAWK 的适用面比四边形不等式更宽。

图 3-1 · Monge、totally monotone、monotone 三个判定的即时检查器。可粘贴任意以空格与换行分隔的数字矩阵，逐条给出判定结果与首个违反处的坐标（1-based）。

4 · SMAWK 的 Reduce 与递归

SMAWK 出自 Aggarwal、Klawe、Moran、Shor 与 Wilber 1987 年的论文，算法名是五人姓氏首字母的重排，读作 smoke [1]。行多列少的「高」矩阵，§2 的奇偶递归已经够用；要害在「宽」矩阵（ $n > m$ ）： $n$ 列里至多 $m$ 列真的持有某行的最左最小值，Reduce 的任务是用 $O(n)$ 次比较甩掉注定无用的列。

工具仍是同一行上的一次比较，但 totally monotone 让一次比较的结论辐射到半列。设 $p < q$ 。若 $M[i, p] \le M[i, q]$ ，则对一切 $h \le i$ 都有 $M[h, p] \le M[h, q]$ （否则行 $\{h, i\}$ 与列 $\{p, q\}$ 交出的 ${2 \times 2}$ 违反 monotone），列 $q$ 从第 $i$ 行向上整段不可能持有任何行的答案；反之若 $M[i, p] > M[i, q]$ ，列 $p$ 从第 $i$ 行向下整段出局。这些「已有足够信息断定 $LM(h) \ne j$ 」的格子称为死格（dead）：一次比较，要么右列上段死，要么左列下段死。

Reduce 用一个列栈组织这些比较，维持三条不变量：栈内列号递增；栈位 $j$ 的列，其上方 $j - 1$ 格已死；不在栈上的列（弹掉的与丢弃的）整列死。进场列 $k$ 与栈顶列在「栈高」那一行比较。栈顶严格更大时，栈顶列自该行向下整段死，其上段由不变量本来就死，于是整列死亡、弹栈，继续与新栈顶比；否则 $k$ 自该行向上整段死、入栈，上方死格数恰好等于新栈位减一；栈高已经等于 $m$ 时 $k$ 整列死，直接丢弃。每次比较之后，要么一列被判死，要么进场列前进，两种事件对每一列各至多发生一次，比较数 $\le 2n$ 。结束时幸存列至多 $m$ 列，且每行的最左最小值都在幸存列里。书中样例上跑一遍：5 列剩 4 列，只花 5 次比较。

主流程把 Reduce 与 §2 的奇偶递归拼起来：先 Reduce 把列数压到不超过行数，对奇数位行递归求解，偶数位行在相邻奇数位行的答案之间插值全扫。递归子问题恰有 $m/2$ 行、至多 $\min(m, n)$ 列，每层的 Reduce 与插值各花线性时间，总计 $O(m + n)$ [1]。

图 4-1 · Reduce 在书中 totally monotone 样例上的逐帧执行。列栈自左向右生长，栈位 j 的列其上方 j−1 格标灰，弹掉或丢弃的列整列灰化，本步比较的两格分别以蓝、红框标出。可单步观察每次比较如何在「弹掉整列」与「进场列前进」之间二选一，读数追踪比较数与 2n 上限。

5 · 弹栈条件的勘误

附录 D 的 Reduce 伪码，弹栈条件写的是 $M[t, S[t]] \ge M[t, k]$ 。正文的死亡论证却只覆盖严格大于： $M[t, S[t]] > M[t, k]$ 时栈顶列下段死，结合不变量整列死。相等的情形落在另一个分支的前提里——取 $\le$ 时死的是进场列 $k$ 的上段，栈顶列一格都没死，按 $\ge$ 把它整列弹掉没有依据。

这个缝隙在书中自己的样例上就能踩到：totally monotone 样例的第 2 行有并列的 14、14。按 $\ge$ 弹栈，列 2 在第 2 行与列 3 的比较中被整列弹掉，而该列下方藏着第 3 行的真最小值 8；随后的递归只能在幸存列里找，第 3 行的答案错成第 4 列的 10，整组输出变成 $[1, 3, 4, 4, 4]$ 而非正确的 $[1, 2, 2, 4, 4]$ 。错的不是「并列时选左还是选右」，是最小值本身。core/smawk.ts 把弹栈条件收紧为严格 $>$ ，并把这组样例锁进 engines.test.ts 的回归；收紧后 $\le 2n$ 的比较计数与三条不变量原样成立， $LM$ 的「最左」口径也保得住。附录 D 自标 Status: Unfinished，这一处大概在待勘误之列。

6 · 小矩阵上的诚实账本

计数口径先分清：暴力与分治计的是比较次数，SMAWK 的实现计的是 lookup 次数，即矩阵元素被读取的次数。lookup 是隐式矩阵下的真实开销：DP 应用里 $M[i][j]$ 往往不是现成数组，而是读到哪格才现算哪格（§1 的两个 $\mathit{OptCost}$ 相加就是），账要按「摸了几格」记。

同一张 ${5 \times 5}$ 样例：暴力 20 次比较，分治 10 次，SMAWK 27 次 lookup，三者里最贵。递归的每一层都重跑一遍 Reduce，插值阶段又会重读栈内的格子，25 格的矩阵被摸了 27 次， $O(m + n)$ 的常数在这个尺寸下没有机会。SMAWK 的优势全在渐近：收益出现在 $n$ 上千、矩阵只以 lookup 形式存在的场合—— $n \times n$ 的隐式矩阵，暴力要摸 $\Theta(n^2)$ 格，SMAWK 只摸 $O(n)$ 格，矩阵有多大与算法摸多少格从此是两个独立的量。

落地的完整例子见落地：SMAWK 加速一维分段 DP：一维分段 DP 的每一层就是一次行最小值，代价矩阵过 isMonge 判定，SMAWK 把每层的工作量从平方压到线性。

7 · 参考文献

Aggarwal, A., Klawe, M. M., Moran, S., Shor, P., & Wilber, R. (1987). Geometric applications of a matrix-searching algorithm. Algorithmica, 2(1), 195–208.
Erickson, J. (2019). Algorithms. Self-published, http://algorithms.wtf. 附录 D 「Advanced Dynamic Programming」（作者标注 Status: Unfinished）。