简介

区间 DP 以区间为研究对象。通常设 $f[l,r]$ 为区间 $[l,r]$ 上的解。$f[l,r]$ 的值通过其子区间的值 $\{f[i,j]:l\le i\le j\le r\}$ 得到。

例

$n$ 堆石子排成一列，第 $i$ 堆石子重量为 $A_i$。每次合并相邻两堆石子，消耗的体力为其重量和。求将所有石子合并为一堆，最少消耗多少体力。

分析

$f[l,r]$：合并第 $l$ 堆至第 $r$ 堆石子的最少体力值。

合并第 $l\cdots r$ 堆石子可分为三步（设 $l\le k<r$）：

1. 合并第 $l\cdots k$ 堆石子，消耗体力值 $f[l,k]$；
2. 合并第 $k+1\cdots r$ 堆石子，消耗体力值为$f[k+1,r]$；
3. 合并剩下两堆石子，消耗体力值 ${\displaystyle \sum _{i=l}^r{A}_i}$。

枚举 $k=l\cdots r-1$，找出最小的体力值。

$$f[l,r]=\underset{l\le k<r}{min}\{f[l,k]+f[k+1,r]\}+\sum _{i=l}^r{A}_i$$

其中 ${\displaystyle \sum _{i=l}^r{A}_i}$ 可以用 前缀和 优化。

状态转移顺序为 $f[$小区间$]\to f[$大区间$]$，故枚举区间长度的 for 循环必须在最外层。

问题的解是 $f[1,n]$。时间复杂度为 $O(n^3)$。

memset(f, 0x7f, sizeof f);

// 预处理前缀和
for (int i = 1; i <= n; i ++) {
    f[i][i] = 0;
    sum[i] = sum[i - 1] + a[i];
}

// 枚举区间长度
for (int len = 2; len <= n; len ++) {
    // 枚举区间左端点
    for (int l = 1; l + len - 1 <= n; l ++) {
        // 计算区间右端点
        int r = l + len - 1;
        for (int k = l; k < r; k ++)
            f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r]);
        f[l][r] += sum[r] - sum[l - 1];
    }
}