← 首页 / DP 加速 · 表格结构换来的时间与空间 待审核 5 页

DP 加速 · 表格结构换来的时间与空间

动态规划的第一课是把递推写对；第二课在教材里常常只剩一句「还可以再优化」。本系列把这句话展开：DP 的加速几乎从不来自更快的代码，而来自表格自身的结构——大部分格子可以不存（滚动数组、Hirschberg 分治）、大部分格子可以不算（稀疏性）、最优决策点的位置有单调性（Knuth、Monge、SMAWK）。五页各取一种结构，每种都配「朴素 vs 优化」的同构对照与实测计数。

内容取材自 Jeff Erickson《Algorithms》的附录 D（见页尾链接），基本引擎与序列对齐 DP、最优分段 DP 两系列衔接：编辑距离与 LCS 的填表在前者，一维分段的递推在后者，本系列在它们之上做减法。

省空间：不存整张表

滚动数组把空间压到 O(m+n)，代价是回溯路径没了；Hirschberg 用分治把路径找回来，时间仍是 O(mn)。

滚动数组 · O(m+n)

省空间：滚动数组与 Hirschberg 分治

编辑距离的递推只依赖上一行，滚动数组把空间从 O(mn) 压到 O(m+n)，代价是回溯路径随表一起丢掉。Hirschberg 分治用正反两遍得分行找出最优路径穿过中线的位置，在同样的空间里把路径找回来，总时间仍是 O(mn) 量级。

省时间：表格里的结构

三种越来越强的结构假设——稀疏（多数格子不用算）、根位置单调（Knuth）、全单调（Monge / SMAWK）——各换一档复杂度。

稀疏 LCS · O(K²)

稀疏性：只在 match point 上递推

经典 LCS 逐格填满 $m \times n$ 的表，携带信息的格子却只有 match point。本页只由匹配点重建整表：排序归并找点、 $O(K^2)$ 稀疏递推； $K = o(\sqrt{mn})$ 时胜过填表，字符重复多时 $K$ 膨胀回 $\Theta(mn)$ 。

根窗口 · O(n²)

Knuth 单调性：最优 BST 的根不回头

最优二叉搜索树的区间 DP 每格枚举全部候选根，总计 O(n³)。Knuth 单调性把每格的枚举夹进两个邻格根之间的窗口，同一对角线望远镜求和为 O(n)，总时间 O(n²)：预设频率下朴素试根 120 次，窗口化 66 次。

SMAWK · O(m+n)

行最小值：Monge 与 SMAWK

许多 DP 的内层是在二维数组的每一行找最小值。行最小值位置单调时，分治做到 O(m + n log m)；totally monotone 矩阵上，SMAWK 做到 O(m + n)，四边形不等式（Monge）是这种结构最常见的来源。

落地：接回一维分段 DP

代价函数满足 Monge 时，分段 DP 的每一层就是一次行最小值问题，SMAWK 把它从平方压到线性。

Monge 分箱 · O(nk)

落地：SMAWK 加速一维分段 DP

排序点列切成 $k$ 个连续箱、最小化各箱跨度的平方和，等宽与等频分箱都不是最优，最优解是一维分段 DP。组代价 $(X_b - X_a)^2$ 满足 Monge，每层递推化成一次隐式矩阵的行最小值，SMAWK 把 $O(n^2 k)$ 压到 $O(nk)$ 。