四边形不等式优化 DP 学习笔记

部分摘自 OI Wiki

四边形不等式优化利用的是状态转移方程中的决策单调性，也常称为 决策单调性优化 DP。

基础知识

考虑最简单的情形，我们要解决如下一系列最优化问题：

$$\begin{array}{}\text{(1)}& f(i)=\underset{1\le j\le i}{min}w(j,i)(1\le i\le n)\end{array}$$

这里假定成本函数 $w(j,i)$ 可以在 $O(1)$ 时间内计算。

NOTE

约定

动态规划的状态转移方程经常可以写作一系列最优化问题的形式。以（1）式为例，这些问题含有参数 $i$，问题的目标函数和可行域都可以依赖于 $i$。每一个问题都是在给定参数 $i$ 时，选取某个可行解 $j$ 来最小化目标函数的取值。为表述方便，下文将参数为 $i$ 的最优化问题简称为「问题 $i$」，该最优化问题的可行解 $j$ 称为「决策 $j$」，目标函数在最优解处取得的值则称为「状态 $f(i)$」。同时，记问题 $i$ 对应的最小最优决策点为 $\mathrm{opt}(i)$。

在一般的情形下，这些问题总时间复杂度为 $O(n^2)$。这是由于对于问题 $i$，我们需要考虑所有可能的决策 $j$。而在满足决策单调性时，可以有效缩小决策空间，优化总复杂度。

• 决策单调性：对于任意 $i_1<i_2$，必然成立 $\mathrm{opt}(i_1)\le \mathrm{opt}(i_2)$。

NOTE

对于问题 $i$，最优决策集合未必是一个区间。决策单调性实际可以定义在最优决策集合上。对于集合 $A$ 和 $B$，可以定义 $A\le B$ 当且仅当对于任意 $a\in A$ 和 $b\in B$，成立 $min\{a,b\}\in A$ 和 $max\{a,b\}\in B$。这蕴含最小（最大）最优决策点的单调性，即此处采取的定义。本文关于最小最优决策点叙述的结论，同样适用于最大最优决策点。但是，存在情形，某更大问题的最小最优决策严格小于另一更小问题的最大最优决策，亦即可能对某些 $i_1<i_2$ 成立 $\mathrm{optmax}(i_1)>\mathrm{optmin}(i_2)$，所以在书写代码时，应保证总是求得最小或最大的最优决策点。

另一方面，拥有相同最小最优决策的问题构成一个区间。这一区间，作为最小最优决策的函数，应严格递增。亦即，给定 $j_1=\mathrm{opt}(i_1)$，$j_2=\mathrm{opt}(i_2)$，如果 $j_1<j_2$，那么必然有 $i_1<i_2$。换言之，如果决策 $j_1<j_2$ 能够成为最小最优决策的问题区间分别是 $[l_{j_1},r_{j_1}]$ 和 $[l_{j_2},r_{j_2}]$，那么必然有 $r_{j_1}<l_{j_2}$。

最常见的判断决策单调性的方法是通过四边形不等式（quadrangle inequality）。在不同的语境下，这一性质也常称为 Monge 性质（用于描述矩阵 $A_{j,i}$）或次模性（submodularity，用于描述以区间为自变量的函数 $f([j,i])$）。

• 四边形不等式：如果对于任意 $a\le b\le c\le d$ 均成立

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

  则称函数 $w$ 满足四边形不等式（简记为「交叉小于包含」）。若等号永远成立，则称函数 $w$ 满足 四边形恒等式。

如果没有特别说明，以下都会保证 $a\le b\le c\le d$。四边形不等式给出了一个决策单调性的充分不必要条件。

定理 1

若 $w$ 满足四边形不等式，则问题 $(1)$ 满足决策单调性。

证明

要证明这一点，可采用反证法。假设对某些 $c<d$，成立 $a=\mathrm{opt}(d)<\mathrm{opt}(c)=b$。此时有 $a<b\le c<d$。根据最优化条件，$w(a,d)\le w(b,d)$ 且 $w(b,c)<w(a,c)$，于是，$w(a,d)-w(b,d)\le 0<w(a,c)-w(b,c)$，这与四边形不等式矛盾。

四边形不等式可以理解在合理的定义域内，$w$ 的二阶混合差分 ${\mathrm{\Delta }}_i{\mathrm{\Delta }}_{j}w(j,i)$ 非正。

利用决策单调性，有很多常见算法都可以将算法复杂度优化到 $O(n\log n)$。这些算法的适用范围、实现难度、运行效率各不相同，需要根据实际场景选择合适的算法。这主要取决于 $w(j,i)$ 的性质。不加说明时，本文默认 $w(i,j)$ 可以 随机访问，即 $w(j,i)$ 可以在 $O(1)$ 时间内查询或计算。但是，并非所有问题中，$w(j,i)$ 都这样容易计算。因此，除了基本情形外，本文还讨论了 $w(j,i)$ 只具有如下性质时，利用决策单调性优化 DP 的方法：

• 移动访问：$w(j,i)$ 可以从 $w(j\pm 1,i)$ 或 $w(j,i\pm 1)$ 以 $O(1)$ 时间转移得到。（类似 莫队算法 中的情形）
• 动态计算：$w(j,i)$ 的计算依赖于 $\{f(j^{\prime }):j^{\prime }<j\}$。这意味着 $f$ 和 $w$ 只能顺次计算。下文介绍了不限制区间个数的区间分拆问题，它就属于这一情形。

这两条性质并不互斥，可能存在 $w(j,i)$ 既需要动态计算，又只支持移动访问的情形。

分治

要求解所有状态，只需要求解所有最优决策点。为了对所有 $1\le i\le n$ 求解 $\mathrm{opt}(i)$，首先计算 $\mathrm{opt}(n/2)$，而后分别计算 $1\le i<n/2$ 和 $n/2<i\le n$ 上的 $\mathrm{opt}(i)$，注意此时已知前半段的 $\mathrm{opt}(i)$ 必然位于 $1$ 和 $\mathrm{opt}(n/2)$ 之间（含端点），而后半段的 $\mathrm{opt}(i)$ 必然位于 $\mathrm{opt}(n/2)$ 和 $n$ 之间（含端点）。对于两个子区间，也类似处理，直至计算出每个问题的最优决策。在分治的过程中记录搜索的上下边界，就可以保证算法复杂度控制在 $O(n\log n)$。递归树层数为 $O(\log n)$，而每层中，单个决策点至多计算两次，所以总的计算次数是 $O(n\log n)$。

除了随机访问的基本情形外，分治算法还可以应用于 $w(j,i)$ 只支持移动访问的情形。只需要在计算过程中维护游标 $(j,i)$ 和相应函数值 $w(j,i)$，在需要查询新的值时，将游标暴力移动到当前位置并更新函数值即可。这样做的时间复杂度仍然为 $O(n\log n)$。对此更为详细的讨论，可以参考下文 简化 LARSCH 算法 一节。但是，分治算法无法解决 $w(j,i)$ 需要动态计算的情形，因为分治算法没有办法在左半区间问题尚未解决时，就计算出区间中点处的最小最优决策 $\mathrm{opt}(n/2)$。

val_t w(int j, int i); // 成本函数
val_t f[N];            // 最优值
int opt[N];            // 最小最优决策

// 递归求解 [l,r] 中的问题
// 已知它们的最小最优决策点一定出现在区间 [opt_l, opt_r] 中
void calc(int l, int r, int opt_l, int opt_r) {
    int mid = (l + r) / 2;
    // 求问题 mid 的最优决策点
    for (int j = opt_l; j <= std::min(opt_r, mid); ++j) {
        if (w(j, mid) < f[mid]) {
            f[mid] = w(j, mid);
            opt[mid] = j;
        }
    }
    // 根据决策单调性得出左右两部分的决策区间，递归处理
    if (l < mid)
        calc(l, mid - 1, opt_l, opt[mid]);
    if (r > mid)
        calc(mid + 1, r, opt[mid], opt_r);
}

// 求解整个区间 [1,n] 的问题
void solve(int n) {
    // 每次调用递归函数前，都需要清空数组 f
    std::fill(f + 1, f + n + 1, inf);
    // 最开始时，只知道问题 [1,n] 的所有决策点都一定在 [1,n] 中
    calc(1, n, 1, n);
}

二分队列

注意到对于每个决策点 $j$，能使其成为最小最优决策点的问题 $i$ 必然构成一个区间。可以通过单调队列记录到目前为止每个决策点可以解决的问题的区间，这样，问题的最优解自然可以通过队列中记录的决策点计算得到。

具体地，算法需要顺次遍历决策点。当遍历到决策点 $k$ 时，队列中需要记录到目前为止每个可行的决策点 $j$ 和能够解决的问题区间左右端点 $l_j$ 和 $r_j$ 构成的 三元组。对于给定区间 $[l_j,r_j]$ 内的问题，$j$ 应该是到目前为止考虑过的决策点（即区间 $[1,k]$ 中的决策点）中最小最优的。每时每刻，队列中存储的决策未必是连续的，但是尚未解决的问题 $[j,n]$ 应该是队列中存储的问题区间的不交并。

为了说明队列更新过程中，决策点 $j$ 是最小最优决策的问题 $i$ 总构成一段连续的区间，需要适当加强前文的结论：

推论 1

设 ${\mathrm{opt}}_k(i)$ 是仅考虑 $[1,k]$ 中的决策时，问题 $i$ 的最小最优决策。如果 $w$ 满足四边形不等式，那么对于任意 $i_1<i_2$，必然成立 ${\mathrm{opt}}_k(i_1)\le {\mathrm{opt}}_k(i_2)$。

证明

设 $M$ 是充分大的正实数。函数 $w^{\prime }(j,i)=w(j,i)+M[j>k]$ 仍然满足四边形不等式，其中，$[\cdot ]$ 是 Iverson 括号。考虑以 $w^{\prime }$ 为成本函数的辅助 DP。在辅助 DP 中，对于任何问题 $i$，决策 $j>k$ 都不可能是最小最优的，即 ${\mathrm{opt}}^{\prime }(i)={\mathrm{opt}}_k^{\prime }(i)={\mathrm{opt}}_k(i)$。对辅助 DP 应用定理 1 就得到本推论。

该算法过程如下：

• 初始时，队列是空的。类似于单调队列，每次考虑下一个决策 $j$ 的时候，都需要进行出队和入队操作。
• 出队：首先将上一个问题 $j-1$ 从队列中移除。如果队首的决策能够解决的问题的右端点恰为 $j-1$，直接弹出队首；否则，将队首决策能够解决问题的左端点更新为 $j$。
• 入队：要对决策 $j$ 进行入队时，首先比较它和队尾的决策 $j^{\prime }$。
  • 如果对于问题 $l_{j^{\prime }}$，将要入队的决策 $j$ 比已有的决策 $j^{\prime }$ 严格更优，即 $w(j,l_{j^{\prime }})<w(j^{\prime },l_{j^{\prime }})$ 时，则弹出队尾的决策 $j^{\prime }$。此操作持续到队列为空或队尾的决策 $j^{\prime }$ 比起 $j$ 对于问题 $l_{j^{\prime }}$ 更优时为止。
  • 如果队列已空，入队 $(j,j,n)$，即认为决策 $j$ 是尚未解决的所有问题的最优解。
  • 如果队尾决策 $j^{\prime }$ 对于问题 $r_{j^{\prime }}$ 同样不劣于将入队的决策 $j$，那么当 $r_{j^{\prime }}<n$ 时，入队 $(j,r_{j^{\prime }}+1,n)$，表示 $j$ 是问题 $[r_{j^{\prime }}+1,n]$ 的最小最优决策；否则，不需要入队 $j$，因为它并不比已有的决策更优。
  • 最后的情形是，队尾决策 $j^{\prime }$ 比起要入队的决策 $j$ 对于问题 $l_{j^{\prime }}$ 严格更优，而对于问题 $r_{j^{\prime }}$ 严格更劣。这说明，存在问题 $i\in (l_{j^{\prime }},r_{j^{\prime }}]$ 使得问题 $[l_{j^{\prime }},i-1]$ 的最小最优决策为 $j^{\prime }$ 且问题 $[i,r_{j^{\prime }}]$ 的最小最优决策为 $j$。因而，需要通过 二分 找到最小的 $i\in [l_{j^{\prime }},r_{j^{\prime }}]$ 使得 $w(j,i)<w(j^{\prime },i)$，再将队尾的区间右端点 $r_{j^{\prime }}$ 修改为 $i-1$，并入队 $(j,i,n)$。
• 处理完决策 $j$ 后，就已经处理了所有到 $j$ 为止的决策。此时，队首决策就是问题 $j$ 的最小最优决策，可以记录相应的最优解。

val_t w(int j, int i); // 成本函数
val_t f[N];            // 最优值
int opt[N];            // 最小最优决策
int lt[N], rt[N];      // 决策 j 可以解决的问题区间 [l_j,r_j]

// 求解整个区间 [1,n] 的问题
void solve(int n) {
    std::deque<int> dq; // 存储所有可行决策的单调队列

    // 顺次考虑所有问题和决策，下标从 1 开始
    for (int j = 1; j <= n; ++j) {
        // 出队
        if (!dq.empty() && rt[dq.front()] < j)
            dq.pop_front();
        if (!dq.empty())
            lt[dq.front()] = j;
        // 入队
        while (!dq.empty() &&
               w(j, lt[dq.back()]) < w(dq.back(), lt[dq.back()])) {
            dq.pop_back();
        }
        if (dq.empty()) {
            lt[j] = j;
            rt[j] = n;
            dq.emplace_back(j);
        } else if (w(j, rt[dq.back()]) >= w(dq.back(), rt[dq.back()])) {
            if (rt[dq.back()] < n) {
                lt[j] = rt[dq.back()] + 1;
                rt[j] = n;
                dq.emplace_back(j);
            }
        } else {
            int ll = lt[dq.back()], rr = rt[dq.back()], i = rr;
            // 二分
            while (ll <= rr) {
                int mm = (ll + rr) / 2;
                if (w(j, mm) < w(dq.back(), mm)) {
                    i = mm;
                    rr = mm - 1;
                } else {
                    ll = mm + 1;
                }
            }
            rt[dq.back()] = i - 1;
            lt[j] = i;
            rt[j] = n;
            dq.emplace_back(j);
        }
        // 计算
        f[j] = w(dq.front(), j);
        opt[j] = dq.front();
    }
}

类似于单调队列，每个决策点至多入队一次，出队一次。其中，出队是 $O(1)$ 的，而入队是 $O(\log n)$ 的（可能需要二分），所以总的时间复杂度是 $O(n\log n)$。

由于二分队列算法顺次考虑所有问题和决策点，它可以应用于 $w(j,i)$ 需要动态计算的情形。这是它相较于分治算法的优势。但是，因为算法中的二分步骤依赖于对 $w(j,i)$ 的随机访问，它无法应用于 $w(j,i)$ 只支持移动访问的情形。

例题 1：「POI2011」Lightning Conductor

给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots ,a_n$，要求对于每一个 $1\le i\le n$，找到最小的非负整数 $f_i$ 满足

$$\mathrm{\forall }j\in [1,n]:a_j\le a_i+f_i-\sqrt{|i-j|}.$$

思路

显然，经过不等式变形，我们可以得到待求整数 $f_i=\underset{j}{max}\{a_j+\sqrt{|i-j|}-a_i\}$。不妨先考虑 $j\le i$ 的情况（另外一种情况类似），此时我们可以得到状态转移方程：

$$f_i=-\underset{j\le i}{min}\{-a_j-\sqrt{i-j}+a_i\}.$$

根据 $-\sqrt{x}$ 的凸性，我们很容易得出（后文将详细描述）函数 $w(l,r)=-a_l-\sqrt{r-l}+a_r$ 满足四边形不等式，因此套用上述的算法便可在 $O(n\log n)$ 的时间内解决此题了。

简化 LARSCH 算法

前两种算法都无法处理 $w(j,i)$ 既需要动态计算，也只支持移动访问的情形。本节介绍一种能够同时克服这两种困难的算法。它是 Larmore 和 Schieber 在 1991 年提出的 LARSCH 算法的简化版本，故称为 简化 LARSCH 算法。该算法的原始版本可以在 $O(n)$ 时间内解决决策单调性 DP 问题，但实现较复杂，本文不做介绍。

仍然考虑分治求解。求解区间 $(l,r]$ 内的问题时，假设如下信息已知：

• 区间 $[1,l]$ 中问题 $i$ 的最小最优决策 $\mathrm{opt}(i)$ 和最优值，以及
• 仅考虑区间 $[1,l]$ 中的决策，问题 $r$ 的最小最优决策 ${\mathrm{opt}}_l(r)$ 和最优值。

区间 $(l,r]$ 内的问题求解结束时，需要得到区间 $(l,r]$ 内问题的最小最优决策和最优值。

设 $\mathit{\text{mid}}$ 为区间 $(l,r]$ 的中点。求解过程如下：

1. 遍历决策 $i\in [\mathrm{opt}(l),{\mathrm{opt}}_l(r)]$，更新问题 $\mathit{\text{mid}}$ 的最小最优决策和最优值。
2. 递归求解区间 $(l,\mathit{\text{mid}}]$ 中的问题。
3. 遍历决策 $i\in (l,\mathit{\text{mid}}]$，更新问题 $r$ 的最小最优决策和最优值。
4. 递归求解区间 $(\mathit{\text{mid}},r]$ 中的问题。

对整个区间 $[1,n]$ 执行递归前，首先需要用决策 $j=1$ 更新问题 $i\in \{1,n\}$。该算法在递归到 $l=r$ 时就终止。

val_t w(int j, int i); // 成本函数
val_t f[N];            // 最优值
int opt[N];            // 最小最优决策

// 用决策 j 更新问题 i
void check(int j, int i) {
    if (w(j, i) < f[i]) {
        f[i] = w(j, i);
        opt[i] = j;
    }
}

// 递归求解区间 (l, r] 内的问题
void calc(int l, int r) {
    int mid = (l + r + 1) / 2;
    for (int j = opt[l]; j <= opt[r]; ++j)
        check(j, mid);
    if (mid < r)
        calc(l, mid);
    for (int j = l + 1; j <= mid; ++j)
        check(j, r);
    if (mid > l)
        calc(mid, r);
}

// 求解整个区间 [1, n] 内的问题
void solve(int n) {
    // 清空 f 数组
    std::fill(f + 1, f + n + 1, inf);
    // 初始化
    check(1, 1);
    check(1, n);
    // 递归求解区间 (1, n] 内的问题
    calc(1, n);
}

首先，可以说明这一算法的正确性。为此，只要检查每一递归求解的步骤（即步骤 2 和 4）前都满足上文给出的前提条件。由前一节得到的推论 1，有 $\mathrm{opt}(l)={\mathrm{opt}}_l(l)\le {\mathrm{opt}}_l(\mathit{\text{mid}})\le {\mathrm{opt}}_l(r)$，所以步骤 1 后，${\mathrm{opt}}_l(\mathit{\text{mid}})$ 是已知的，进而执行步骤 2 前递归求解区间 $(l,\mathit{\text{mid}}]$ 中问题的前提条件成立。由于之前 $\{\mathrm{opt}(i):i\in [1,l]\}$ 是已知的，步骤 2 又得到了 $\{\mathrm{opt}(i):i\in (l,\mathit{\text{mid}}]\}$ 的取值，所以这之后 $\{\mathrm{opt}(i):i\in [1,\mathit{\text{mid}}]\}$ 都是已知的；同时，由于之前 ${\mathrm{opt}}_l(r)$ 是已知的，步骤 3 后，${\mathrm{opt}}_{\mathit{\text{mid}}}(r)$ 就也是已知的。因此，执行步骤 4 前递归求解区间 $(\mathit{\text{mid}},r]$ 中问题的前提条件也成立。

然后，需要说明该算法的复杂度仍然是 $O(n\log n)$ 的。递归树的层数是 $O(\log n)$ 的。对于递归树中的同一层的每个结点，分别遍历区间 $[\mathrm{opt}(l),{\mathrm{opt}}_l(r)]$ 和 $(l,\mathit{\text{mid}}]$ 中的决策。因为 $\mathrm{opt}(l)\le {\mathrm{opt}}_l(r)\le \mathrm{opt}(r)$，所以在同一层中，每个决策点只遍历了 $O(1)$ 次。故而，递归树的每一层中总的遍历次数是 $O(n)$ 的。假设单次访问或计算 $w(j,i)$ 的复杂度是 $O(1)$ 的，算法的时间复杂度就是 $O(n\log n)$ 的。

对于一些 $w(j,i)$ 只支持移动访问的情形，这一算法的复杂度仍然是 $O(n\log n)$ 的。此时，需要为算法流程中的步骤 1 和步骤 3 分别维护游标 $(j,i)$ 和 $w(j,i)$ 的当前取值。每次需要访问新的值时，需要将游标 $(j,i)$ 从上一次访问时的位置暴力更新到当前位置，并对函数值 $w(j,i)$ 进行转移。容易验证，当对递归树进行遍历时，这些暴力更新的总次数是 $O(n\log n)$ 的。所以，算法的时间复杂度仍然是 $O(n\log n)$ 的。

NOTE

非随机访问的复杂度证明

只需要证明游标移动的总次数是 $O(n\log n)$ 的。设 $A$ 和 $B$ 分别为步骤 1 和 3 对应的游标。实际上可以保证：在求解区间 $(l,r]$ 的问题之前，游标 $A$ 处于位置 $(\mathrm{opt}(l),l)$，游标 $B$ 处于位置 $(l,l)$；而在这之后，游标 $A$ 处于位置 $(\mathrm{opt}(r),r)$，游标 $B$ 处于位置 $(r,r)$。

考虑构造如下游标移动规则。步骤 1 中，可以令游标 $A$ 沿着路径

$$(\mathrm{opt}(l),l)\to (\mathrm{opt}(l),\mathit{\text{mid}})\to ({\mathrm{opt}}_l(r),\mathit{\text{mid}})\to (\mathrm{opt}(l),\mathit{\text{mid}})\to (\mathrm{opt}(l),l)$$

移动。此时，游标 $A$ 和 $B$ 均处于求解区间 $(l,\mathit{\text{mid}}]$ 的问题之前的规定位置上。步骤 2 中，按规定，游标 $A$ 将移动到 $(\mathrm{opt}(\mathit{\text{mid}}),\mathit{\text{mid}})$，游标 $B$ 将移动到 $(\mathit{\text{mid}},\mathit{\text{mid}})$。步骤 3 中，可以令游标 $B$ 沿着路径

$$(\mathit{\text{mid}},\mathit{\text{mid}})\to (l,\mathit{\text{mid}})\to (l,r)\to (\mathit{\text{mid}},r)\to (\mathit{\text{mid}},\mathit{\text{mid}})$$

移动。此时，游标 $A$ 和 $B$ 均处于求解区间 $(\mathit{\text{mid}},r]$ 的问题之前的规定位置上。步骤 4 中，按规定，游标 $A$ 将移动到 $(\mathrm{opt}(r),r)$，游标 $B$ 将移动到 $(r,r)$。两个游标均在结束求解区间 $(l,r]$ 的问题的规定位置上。因此，这一移动规则符合上述规定。而且，该移动规则足以完成步骤 1 和 3 中的所有计算。直接计算该规则中游标的移动次数可知，步骤 1 需要

$$2({\mathrm{opt}}_l(r)-\mathrm{opt}(l))+2(\mathit{\text{mid}}-l)$$

次移动，步骤 3 需要

$$2(\mathit{\text{mid}}-l)+2(r-\mathit{\text{mid}})=2(r-l)$$

次移动。将这些移动次数对递归树中的所有结点求和，利用同一层中的所有 $[l,r]$ 和 $[\mathrm{opt}(l),{\mathrm{opt}}_l(r)]$ 至多只在端点处重合这一性质，就可以说明总的移动次数是 $O(n\log n)$ 的。

由于上述移动规则比起实际计算时游标的移动设置了更多的途径点，所以游标的实际移动次数不会超过该规则下移动次数的估计。因此，游标的实际移动次数也是 $O(n\log n)$ 的。

由于该算法在求解区间 $(l,r]$ 的问题前，已经计算出了区间 $[1,l]$ 中的最优解 $f(i)$，所以该算法也可以应用于 $w(j,i)$ 需要动态计算的情形。

区间分拆问题

考虑将某个区间拆分成若干个子区间的问题。形式化地说，将给定区间 $[1,n]$ 拆分成 $[a_1,b_1],\cdots ,[a_k,b_k]$，其中，$a_1=1$，$b_k=n$，以及 $b_i+1=a_{i+1}$ 对任意 $i<k$ 都成立。对于给定拆分，成本为 $\sum _{i=1}^{k}w(a_i,b_i)$。问题要求最小化这一成本。可以列出如下的 $1D\to 1D$ 状态转移方程。

$$f(i)=\underset{1\le j\le i}{min}[f(j-1)+w(j,i)](1\le i\le n)$$

这里，$f(0)=0$。注意到，只要 $w(j,i)$ 满足四边形不等式，$f(j-1)+w(j,i)$ 必然满足四边形不等式，因为第一项并不包括 $j$ 和 $i$ 的交叉项，在混合差分时会消去。但是由于成本函数依赖于前面的子问题，这一转移只能够顺序计算，所以无法应用前文描述的第一种分治算法，通常只适合应用二分队列算法或简化 LARSCH 算法。算法复杂度为 $O(n\log n)$

---