我的算法书 - 四边形不等式优化

一句话算法

如果区间 DP 的最优断点会随着区间端点单调移动，就只在相邻区间的最优断点之间枚举。

问题模型

考虑一类区间 DP：

dp[l][r]=\min_{l\le k<r}\{dp[l][k]+dp[k+1][r]+w(l,r)\}

其中 w(l,r) 是合并整个区间 [l,r] 的代价。

朴素做法要枚举：

区间长度；
左端点 l；
分割点 k。

因此时间复杂度是 $O(n^3)$ 。

如果最优分割点满足：

opt[l][r-1]\le opt[l][r]\le opt[l+1][r]

那么计算 dp[l][r] 时，不需要枚举所有 k，只需要枚举：

k\in[opt[l][r-1],opt[l+1][r]]

这就是四边形不等式优化在区间 DP 中最常见的形态，也常被称为 Knuth 优化。

核心直觉

区间右端点变大时，最优断点通常不会往左跳；区间左端点变大时，最优断点通常不会往左侧外面跑。

以石子合并为例：

dp[l][r] 表示把第 l..r 堆石子合成一堆的最小代价；
最后一次合并一定把 [l,k] 和 [k+1,r] 两段合起来；
合并代价是区间总和 sum(l,r)。

当区间向右扩展时，右侧石子更多，最优断点倾向于右移，而不是突然回到很左的位置。这种“最优决策点单调移动”的性质，就是优化的入口。

“记忆方式”

先算短区间，再算长区间；长区间的断点，只在两个相邻短区间的断点之间找。

四边形不等式

设 $w(l,r)$ 是区间代价函数。若对任意：

a\le b\le c\le d

都有：

w(a,c)+w(b,d)\le w(a,d)+w(b,c)

则称 $w$ 满足四边形不等式。

在区间 DP 优化中，还常需要区间包含单调性：

w(b,c)\le w(a,d)

直观地说，外层大区间的代价不小于内部小区间。

石子合并中：

w(l,r)=\sum_{i=l}^{r}a_i

只要石子重量非负，区间和天然满足包含单调性。并且对 $a\le b\le c\le d$ ：

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

所以它满足四边形不等式。

算法步骤

以石子合并为例。

预处理前缀和，用 $O(1)$ 求 sum(l,r)。
初始化：

$dp[i][i]=0,\quad opt[i][i]=i$
按区间长度从小到大枚举 len。
对每个区间 [l,r]，只枚举：

$k\in[opt[l][r-1],opt[l+1][r]]$
用转移式更新：

$dp[l][r]=dp[l][k]+dp[k+1][r]+sum(l,r)$
记录让 dp[l][r] 最小的 k 到 opt[l][r]。

算法证明

为什么能缩小枚举范围

四边形不等式和区间包含单调性可以推出区间 DP 的决策单调性：

opt[l][r-1]\le opt[l][r]\le opt[l+1][r]

这个结论的含义是：

固定左端点 l，右端点从 r-1 扩到 r，最优断点不会左移到 opt[l][r-1] 左侧；
固定右端点 r，左端点从 l+1 扩到 l，最优断点不会右移到 opt[l+1][r] 右侧。

因此 dp[l][r] 的真正最优断点一定落在：

[opt[l][r-1],opt[l+1][r]]

只枚举这个范围不会漏解。

为什么复杂度变成平方级

朴素区间 DP 中，每个区间都枚举 $O(n)$ 个断点，因此总复杂度为：

O(n^2)\times O(n)=O(n^3)

使用决策单调性后，虽然单个区间的窗口长度不一定为常数，但所有窗口由相邻 opt 值夹住，整体不会反复扫完整段。实际模板按长度转移时，总复杂度为 $O(n^2)$ 。

更重要的是，代码层面每个 dp[l][r] 都只访问一个很短的候选区间，在石子合并、最优二叉搜索树等经典模型中能稳定把三重循环降到二重循环级别。

复杂度分析

朴素区间 DP：时间复杂度 $O(n^3)$ ，空间复杂度 $O(n^2)$ 。
四边形不等式优化后：时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ 。

如果只需要答案但仍要依赖相邻区间的 opt，通常仍保留二维 dp 和 opt。

代码实现

下面代码解决线性石子合并的最小代价问题。

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

        #include <bits/stdc++.h>
using namespace std;

const long long INF = (1LL << 62);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<long long> a(n + 1), prefix(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        prefix[i] = prefix[i - 1] + a[i];
    }

    auto sum = [&](int l, int r) {
        return prefix[r] - prefix[l - 1];
    };

    vector<vector<long long>> dp(n + 2, vector<long long>(n + 2, 0));
    vector<vector<int>> opt(n + 2, vector<int>(n + 2, 0));

    for (int i = 1; i <= n; i++) {
        opt[i][i] = i;
    }

    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            dp[l][r] = INF;

            int left = opt[l][r - 1];
            int right = opt[l + 1][r];
            left = max(left, l);
            right = min(right, r - 1);

            for (int k = left; k <= right; k++) {
                long long cur = dp[l][k] + dp[k + 1][r] + sum(l, r);
                if (cur < dp[l][r]) {
                    dp[l][r] = cur;
                    opt[l][r] = k;
                }
            }
        }
    }

    cout << dp[1][n] << '\n';
    return 0;
}

测试用例

输入：

4
4 1 1 4

输出：

一种最优合并过程：

1 + 1 = 2, 代价 2
4 + 2 = 6, 代价 6
6 + 4 = 10, 代价 10
总费用 2 + 6 + 10 = 18

应用分类详解

四边形不等式优化的本质是利用“最优决策点单调”减少 DP 转移枚举。看到区间 DP、转移枚举断点、代价满足区间单调时，可以考虑它。

一、区间合并 DP

典型模式： 把一段连续对象合并成一个整体，最后一步枚举断点。

识别信号： 转移形如 dp[l][r] = min(dp[l][k] + dp[k+1][r] + cost(l,r))。

核心建模： 若 cost(l,r) 满足四边形不等式和包含单调性，就维护 opt[l][r] 缩小断点范围。

应用场景	经典题目	核心思路
线性石子合并	石子合并最小代价	区间和作为合并代价
最优二叉搜索树	Knuth 经典模型	根节点选择具有单调性
文件合并	合并连续文件	合并代价是区间权值和

二、二维区间最优断点

典型模式： 需要记录每个区间的最佳分割点。

识别信号： k 的最优位置随区间边界移动呈单调变化。

核心建模： 用 opt[l][r-1] 和 opt[l+1][r] 夹住 opt[l][r]。

三、一维决策单调 DP

典型模式： 转移形如：

dp[i]=\min_{j<i}\{dp[j]+w(j,i)\}

识别信号： 最优 j 随 i 增大而不下降。

核心建模： 这时通常使用单调队列、分治优化或维护决策区间，而不是本文的区间 DP 模板。

经典例题

1. 线性石子合并

练习本文模板。重点是写对 opt[i][i] = i，以及枚举断点时右端点不能超过 r-1。

2. 最优二叉搜索树

Knuth 优化的经典来源。状态是区间内关键字构成的最优搜索树，转移枚举根节点。

3. 文件连续合并

与石子合并模型相同。若每次只能合并相邻文件，且代价为文件大小和，就可以套用区间 DP 与四边形不等式优化。

参考

本书决策单调性章节：dynamic_programming/decision_mono/index.md
Knuth, Optimum binary search trees
Frances Yao, Efficient dynamic programming using quadrangle inequalities