Monge 分箱 · O(nk)

落地：SMAWK 加速一维分段 DP

行最小值：Monge 与 SMAWK 把 SMAWK 当作一个独立的矩阵搜索算法讲完，留下的问题是 DP 里哪来那么多现成的 Monge 矩阵。本页给出一个完整的落地案例，取自 Erickson 附录 D 的习题 5 与习题 6 [1]：把一列排序的数切成 $k$ 个连续箱，最小化各箱跨度的平方和。这个代价满足 Monge 条件，分段 DP 的每一层递推化成一次行最小值，总时间从 $O(n^2 k)$ 降到 $O(nk)$ 。

1 · 从分箱到一维分段 DP

考试成绩、接口延迟采样这类一维数据，常用直方图压成一眼能读的摘要。变宽直方图（variable-width histogram）不要求箱等宽，箱界可以任选，「箱界放哪」于是成了优化问题：Erickson 附录 D 的习题 6 用它总结全校学生的绩点 [1]。本页取姊妹题（习题 5）的纯几何代价，称 k 区间覆盖（k-interval cover）：给定排序互异的 $X_0 < X_1 < \dots < X_{n-1}$ 与正整数 $k$ ，选 $k$ 个区间盖住全部点，最小化区间长度的平方和。平方专罚悬殊，最优的 $k$ 个区间会长短相近；习题 6 的箱代价还要乘上箱内点数，同属一维分段，本页不展开。

工程里现成的两种分法都不碰优化。等宽分箱（equal-width）把值域 $[X_0, X_{n-1}]$ 均分成 $k$ 段，密集区与稀疏区一视同仁，还可能产出一个点也没有的空箱；等频分箱（equal-frequency）给每箱约 $n/k$ 个点，箱内点数齐了，跨度却听天由命。最优解得回到结构上：最优的 $k$ 个区间必然把点列按下标切成 $k$ 个连续组，一组从第 $a$ 点延伸到第 $b$ 点时，最短的覆盖区间就是 $[X_a, X_b]$ ，代价

w(a, b) = (X_b - X_a)^2

问题至此变成枚举最后一段：相册排版与内容分栏里的一维分段 DP：同一套「枚举最后一段」递推，段代价换成 $w$ ，聚合取和。朴素实现里每层的每个终点都要扫一遍全部起点， $k$ 层合计 $O(n^2 k)$ 。

2 · 组代价的 Monge 性

$w$ 继承了平方函数的凸性，这份凸性落到矩阵语言里就是 Monge 条件。

定理 2.1 排序互异的点列上， $w(a, b) = (X_b - X_a)^2$ 满足四边形不等式：对一切 $a < a'$ 与 $b < b'$ ， $w(a, b) + w(a', b') \le w(a, b') + w(a', b)$ 。

证明 Monge 性等价于全部相邻 ${2 \times 2}$ 子阵满足不等式，只需验证 $a' = a + 1$ 、 $b' = b + 1$ 的情形。记 $s = X_b - X_{a+1}$ 、 $p = X_{a+1} - X_a$ 、 $q = X_{b+1} - X_b$ ，点列互异保证 $p, q > 0$ 。左边为 $(s + p)^2 + (s + q)^2$ ，右边为 $(s + p + q)^2 + s^2$ ，右边减左边恒等于 ${2pq > 0}$ ，与 $s$ 的符号无关。∎

这条不等式还有一个不看代数的读法。四个下标给出两种配对方式：交错配对取区间 $[X_a, X_b]$ 与 $[X_{a'}, X_{b'}]$ ，嵌套配对取 $[X_a, X_{b'}]$ 与 $[X_{a'}, X_b]$ 。两种配对的总长度相同，嵌套的一对一长一短，交错的一对更均匀，凸的代价函数罚的就是悬殊，嵌套配对更贵。引擎侧的核对同样只查相邻 ${2 \times 2}$ ：costMatrix 把 $w$ 铺成显式矩阵，isMonge 在预设与随机点列上逐格验证，测试把这一性质锁死。

3 · 每层递推与隐式矩阵

记 $D_g[t]$ 为「前 $t$ 个点（下标 ${0}$ 到 $t-1$ ）切成 $g$ 箱」的最优代价。最后一箱含下标 $s$ 到 $t-1$ ，前 $s$ 个点交给上一层：

D_g[t] \;=\; \min_{s < t} \big(\, D_{g-1}[s] + w(s,\ t-1) \,\big)

固定层号 $g$ ，右边就是矩阵 $M[t][s] = D_{g-1}[s] + w(s, t-1)$ 的第 $t$ 行最小值：一整层递推等于一次「求全部行最小值」。 $M$ 由 Monge 的 $w$ 加上一项只随列号变化的 $D_{g-1}[s]$ 平移而来，四边形不等式两边同增同减，Monge 性原样保留。

真正接上 SMAWK 之前还有两道坎。其一是非法格子： $s \ge t$ 时「最后一箱」一个点也分不到，dpSmawk 给这些格子补 $\infty$ 。它们聚成矩阵的右上三角，这片区域向上、向右封闭，四边形不等式的四项里总是右上角那一项最先变成 $\infty$ ，左边一旦出现 $\infty$ 右边必然同为 $\infty$ ，不等式从不被破坏。其二是矩阵从未被建出：显式铺一张 $n \times n$ 的表本身就要 $\Theta(n^2)$ 时间，优化直接归零。dpSmawk 传给 smawkRowMinima 的只是一个 lookup 函数，SMAWK 要哪格就现算哪格，每格 $O(1)$ ；Erickson 在 D.7 节用同一手法把平面二部图上的 Bellman–Ford 压到 $O(n^2)$ ，并特意强调矩阵从未被显式构造 [1]。

每层 $O(n)$ 次 lookup 找出全部行最小值 [2]， $k$ 层合计 $O(nk)$ ，对照朴素的 $O(n^2 k)$ ——这正是习题 5(c) 索要的复杂度 [1]。

4 · 对照实验与工作量账本

预设取 24 个成绩样本，分布在 3 到 99 之间，其中有两道宽 13 分的缝（31 到 44、70 到 83）。 $k = 4$ 时三档答案分开得干脆：等宽分箱总代价 1402，等频 2124，DP 最优 1222，与暴力枚举全部切法的 oracle 一致（测试锁死）。等频输得最多，它只数点数不看跨度，两个中段箱各自横跨 29 分；DP 把两道缝都用作箱界，缝的宽度一分也不计入任何箱。等宽这次运气不差，四箱都非空，但它的箱界钉死在值域的四等分点上，只撞上了两道缝中的一道，数据一换就可能冒出空箱。

工作量的口径预先对齐：dpPlain 计内层 $(s, t)$ 对的求值次数，dpSmawk 计 lookup 调用次数，两者都含首层 24 次前缀代价求值。同一份预设上朴素 784 次、SMAWK 578 次，而两档引擎给出的最优代价与全部逐层数值逐位一致（测试断言）。

图 4-1 · 变宽直方图分箱的三档对照。等宽、等频与 DP 最优各占一行，箱按序染色、箱内标注跨度平方，等宽档的空箱以虚线如实显示；可调

k

、切换预设或粘贴自定义数字列表（空格、逗号或换行分隔），读数行实时对比 dpPlain 与 dpSmawk 的求值次数。

5 · 收益的边界

SMAWK 砍的只是层内。 $D_g$ 的每一格都以整层 $D_{g-1}$ 为输入，层与层之间是硬依赖， $O(nk)$ 里的 $k$ 一步也省不掉。层内的收益也没有渐近分析暗示的那么快兑现：写本页之前的预期是「一边平方一边线性，预设上该是碾压」，实测 24 点只从 784 砍到 578，省约 26%。追进 smawkRowMinima 才看清缘由：它不做记忆化，Reduce 阶段与偶数位行的插值会对同一格反复求值，预设与均匀点列上实测每行 8 到 10 次 lookup， $O(m + n)$ 里的常数在 $n = 24$ 时吃掉了大半收益。点列拉到 60 个（0 到 177 间隔 3），差距才拉开到 3.1 倍（5194 对 1682）。两组数字都原样给出，只报 60 点那一组，对常数的判断就会失真。

图 5-1 · 均匀间隔点列上朴素递推与 SMAWK 的求值次数随

n

的增长曲线。可调

k

与标尺位置，读出任一

n

处的两档计数与倍率；

k = 4

时把标尺移到

n = 24

与

n = 60

，可复现正文的 784 对 578 与 5194 对 1682。

适用范围也有一条边界。本页的问题逐层分明，第 $g$ 层只读第 $g - 1$ 层，一层算完再开下一层，SMAWK 的离线形态直接可用。同族的更大分段问题未必如此：枚举最后一段：相册排版与内容分栏里的相册 justified 排版与 Knuth–Plass 断行不限段数，单层递推里 $D[t]$ 依赖同层更早的 $D[s]$ ，矩阵的列值边算边生，离线的 SMAWK 接不上，要换 Larmore–Schieber 的在线变体 [3]。

6 · 参考文献

Erickson, J. (2019). Algorithms (1st ed.). Self-published, appendix D: Advanced dynamic programming, §D.7 & exercises 5–6. http://algorithms.wtf
Aggarwal, A., Klawe, M. M., Moran, S., Shor, P., & Wilber, R. (1987). Geometric applications of a matrix-searching algorithm. Algorithmica, 2(1), 195–208.
Larmore, L. L., & Schieber, B. (1991). On-line dynamic programming with applications to the prediction of RNA secondary structure. Journal of Algorithms, 12(3), 490–515.