对于区间DP问题，都可以列出转移方程： $$ f[i][j] = \smash{\displaystyle\min_{i \le k \le j-1}} F(i, j, k) $$

其中

$$ F(i, j, k) = f[i][k] + f[k+1][j] + cost(i, j) $$

令 $p(i,j)$ 表示使 $f[i][j]$ 最优的 $k$

如果 $cost$ 满足：

  1. 区间包含单调性：$cost(a,d) \ge cost(b,c)$ 对于所有 $a \le b \le c \le d$
  2. 四边形不等式：$cost(i,j-1) + cost(i+1,j) \le cost(i,j) + cost(i+1,j-1)$ 对于所有 $i+1<j-1$

那么对于所有 $j-i+1 \ge 3$ 有 $p(i,j-1) \le p(i,j) \le p(i+1,j)$

这样在枚举决策就只用枚举 $p(i,j-1)$ 到 $p(i+1,j)$ 了

当然，要注意边界情况，即 $F(i,i)$ 和 $F(i,i+1)$

显然这会让复杂度从 $\mathcal{O}(n^3)$ 降低到 $\mathcal{O}(n^2)$（均摊枚举决策的循环）

证明在这篇论文里（这个优化英文叫 Knuth-Yao quadruple inequality speed-up）

就算$cost$与$k$也有关，只要它的前两个参数满足上面两个条件，优化还是能用，证明在这篇论文里


struct Opt {
    int v, k;
} f[N][N];

int F(int i, int j, int k);

void DP() {
    for (int i = 1; i <= n; i++) {
        f[i][i] = (Opt){0, -1};
        for (int j = i + 1; j <= n; j++) {
            f[i][j] = (Opt){1 << 30, -1};
        }
    }
    for (int i = 1; i < n; i++) {
        f[i][i+1] = (Opt){F(i, i+1, i), i};
    }
    for (int len = 3; len <= n; len++) {
        for (int i = 1, j = len; j <= n; i++, j++) {
            int kl = f[i][j - 1].k;
            int kr = f[i + 1][j].k;
            for (int k = kl; k <= kr; k++) {
                int v = F(i, j, k);
                if (v <= f[i][j].v) {
                    f[i][j] = (Opt){v, k};
                }
            }
        }
    }
    printf("%d\n", f[1][n].v);
}