算法刷题系列（五十二）：区间 DP——按区间长度逐步合并子问题

算法刷题系列（五十二）：区间 DP——按区间长度逐步合并子问题

区间 DP 的状态对应连续片段 [left, right]。如果一个区间的最优答案能由更短区间拼接得到，就可以从短到长计算。本文用“矩阵链乘法的标量乘法次数最小化”说明这种依赖关系。

给定矩阵链 A0, A1, ..., A(n-1)。矩阵 Ai 的维度为 dims[i] × dims[i+1]。矩阵乘法满足结合律，因此可以选择不同加括号方式；目标是在不改变矩阵顺序的前提下，使标量乘法次数最少。

一、状态与分割点

定义：

dp[left][right] = 将矩阵 A_left ... A_right 相乘所需的最少标量乘法次数

单个矩阵不需要乘法，故 dp[i][i] = 0。若最后一次乘法在 split 处分割链条，则先分别算出左右结果，再将两个结果相乘：

dp[left][right] =
    min(dp[left][split] + dp[split + 1][right]
        + dims[left] * dims[split + 1] * dims[right + 1])

分割点满足 left <= split < right。左结果的维度是 dims[left] × dims[split+1]，右结果的维度是 dims[split+1] × dims[right+1]，这解释了最后的乘法代价。

二、为什么按区间长度递增

计算 [left, right] 时，转移会读取它左右两侧的更短区间。若按长度从 1 增大到 n，这些状态都已完成。只按左端点或右端点遍历，可能会读取尚未计算的子区间。

三、例子：三张矩阵

令维度数组为 [10, 30, 5, 60]，矩阵尺寸依次为 10×30、30×5、5×60。

• 先乘前两张：10×30×5 + 10×5×60 = 1500 + 3000 = 4500；
• 先乘后两张：30×5×60 + 10×30×60 = 9000 + 18000 = 27000。

所以最优次数为 4500。两种括号次序不改变数学结果，但中间矩阵尺寸不同，代价差异很大。

四、正确性说明

任意完整乘法方案的最后一步一定把当前链分成两个非空连续部分 [left, split] 和 [split+1, right]。如果这两个部分不是各自最优，那么替换成各自更便宜的方案不会改变结果矩阵维度，却会降低总成本，与原方案最优矛盾。因此最优方案必然由两个子区间最优值和最后一次相乘代价组成。枚举所有分割点即可覆盖每一种可能的最后乘法位置，取其中最小值就是最优答案。

五、Java 实现

public class IntervalDp {
    public static long minMatrixMultiplicationCost(int[] dims) {
        if (dims == null || dims.length < 2) {
            throw new IllegalArgumentException("at least one matrix is required");
        }
        for (int dimension : dims) {
            if (dimension <= 0) {
                throw new IllegalArgumentException("dimensions must be positive");
            }
        }

        int n = dims.length - 1;
        long[][] dp = new long[n][n];
        for (int length = 2; length <= n; length++) {
            for (int left = 0; left + length <= n; left++) {
                int right = left + length - 1;
                long best = Long.MAX_VALUE;
                for (int split = left; split < right; split++) {
                    long cost = dp[left][split] + dp[split + 1][right]
                            + (long) dims[left] * dims[split + 1] * dims[right + 1];
                    best = Math.min(best, cost);
                }
                dp[left][right] = best;
            }
        }
        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        if (minMatrixMultiplicationCost(new int[]{10, 30, 5, 60}) != 4500
                || minMatrixMultiplicationCost(new int[]{7, 9}) != 0) {
            throw new AssertionError("interval DP test failed");
        }
    }
}

将乘法的第一个维度转换为 long，使乘法链的中间结果以 64 位计算。

六、Python 实现

def min_matrix_multiplication_cost(dims):
    if dims is None or len(dims) < 2:
        raise ValueError("at least one matrix is required")
    if any(dimension <= 0 for dimension in dims):
        raise ValueError("dimensions must be positive")

    n = len(dims) - 1
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for left in range(n - length + 1):
            right = left + length - 1
            dp[left][right] = min(
                dp[left][split]
                + dp[split + 1][right]
                + dims[left] * dims[split + 1] * dims[right + 1]
                for split in range(left, right)
            )
    return dp[0][n - 1]

assert min_matrix_multiplication_cost([10, 30, 5, 60]) == 4500
assert min_matrix_multiplication_cost([7, 9]) == 0

七、复杂度与适用范围

共有 O(n²) 个区间状态，每个状态枚举 O(n) 个分割点，因此时间复杂度为 O(n³)，空间复杂度为 O(n²)。这里 n 是矩阵数量，不是维度值。

区间 DP 常见于合并、切分、括号化、回文区间等问题。需要确认子问题仍是连续区间，并且某个最后操作能将大区间拆成更小且已定义的区间。

八、边界与常见错误

1. 区间端点混用：本例 dp[left][right] 是闭区间；维度数组右侧使用 dims[right+1]。
2. 遗漏单元素初值：单张矩阵的乘法代价是 0。
3. 错误遍历顺序：必须先有短区间，再算长区间。
4. 分割点右边界写成 <= right：右子区间至少包含一张矩阵，因此最大 split 是 right - 1。
5. 把输入矩阵值误当成维度：矩阵链乘法只需要尺寸序列。
6. 整数乘法溢出：Java 先转成 long 再相乘。

小结

区间 DP 用连续片段定义状态，按长度递增满足子区间依赖。写转移时，明确最后一次切分或合并位置，再枚举所有可能边界。矩阵链的状态、分割点与乘法成本直接展示了这一套路。