核心概述
Knuth 优化 DP：当区间型 DP 满足四边形不等式与决策单调性时，通过预处理与单调性剪枝，将三重循环的 O(n^3) 优化为 O(n^2)。
原文引述
Description: Optimize DP with quadrangle inequality: opt[l][i] ≤ opt[l][i+1] ≤ opt[l+1][i+1]. Precompute optimal split points to reduce O(n^3) DP to O(n^2).（摘自本节点现有英文注释） Time: Precomputation O(n^2); DP O(n^2)（摘自本节点现有英文注释） Status: tested（摘自本节点现有英文注释）
展开阐述
-
适用条件
- DP 形式：dp[l][r] = min_{k∈[l,r)} (dp[l][k] + dp[k+1][r] + cost(l,k,r))。
- 四边形不等式：w[a][c] + w[b][d] ≤ w[a][d] + w[b][c]（对于 l≤a≤b≤c≤d≤r）。
- 单调性：决策点 opt[l][r] 关于 l 非减，关于 r 非减。
-
核心流程
- 预处理决策点：
- 对每个区间长度 len=2..n，计算 opt[l][r]。
- 利用已知的 opt[l][r−1] 和 opt[l+1][r] 来缩小搜索范围。
- DP 计算：
- 使用预处理的 opt[l][r] 限制 k 的范围，避免 O(n^3) 枚举。
- 路径回溯：
- 从 dp[0][n-1] 依次根据 opt 记录重构解。
- 预处理决策点：
-
代码框架（矩阵链乘）
for (int len = 2; len <= n; ++len) {
for (int l = 0; l + len <= n; ++l) {
int r = l + len;
int opt = opt[l+1][r];
ll best = INF;
for (int k = opt[l][r-1]; k <= opt[l+1][r]; ++k) {
ll cur = dp[l][k] + dp[k+1][r] + dims[l]*dims[k+1]*dims[r+1];
if (cur < best) { best = cur; opt[l][r] = k; }
}
dp[l][r] = best;
}
}-
复杂度与边界
- 预处理：每个区间长度 O(n)，总计 O(n^2)。
- DP：每个区间仅搜索 O(1) 的 k 范围，总计 O(n^2)。
- 不满足四边形不等式或单调性将导致错误优化，应先验证条件。
-
典型适用
- 矩阵链乘、括号匹配、最优二分搜索树、凸多边形三角剖分等满足条件的区间型 DP。
-
正确性要点
- 依赖“决策点单调性”与“代价四边形不等式”的共同成立。
- 记录 opt 数组便于解的重构与校验。