区间 DP

区间 DP 以区间为研究对象. 通常设 $f[l,r]$ 为区间 $[l,r]$ 的值，用 $f[小区间]$ 的值推出 $f[大区间]$ 的值.

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

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

合并第 $l\sim r$ 堆石子可分为三步（设 $k$ 为 $[l, r)$ 中的某个数）：

• 合并第 $l\sim k$ 堆石子，消耗体力值 $f[l,k]$.

• 合并第 $k+1\sim r$ 堆石子，消耗体力值为$f[k+1,r]$.

• 合并剩下两堆石子，消耗体力值 $\displaystyle\sum_{i=l}^r A_i$.

枚举 $k$，找出最小的体力值.

$$f[l,r]=\min_{l≤k< r}\{f[l,k]+f[k+1,r]\}+\sum_{i=l}^r A_i$$

其中 $\displaystyle\sum_{i=l}^r A_i$ 可以用 前缀和 优化.

计算顺序为 $f[小区间]\rightarrow f[大区间]$，故枚举区间长度的循环在最外层.

时间复杂度为 $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];
    }
}