区间 DP 的状态定义

最常见的状态定义是使用二维数组 dp[i][j] 来表示区间 [i, j] 上的最优解。

dp[i][j] 的具体含义取决于问题：

• 求解区间 [i, j] 的 最小值或最大值（例如合并石子）。
• 求解处理区间 [i, j] 所需的 最小或最大代价（例如矩阵链乘法）。
• 判断区间 [i, j] 是否满足 某种性质（例如括号匹配）。
• 计算区间 [i, j] 上的 方案数。

区间示例演示

假设我们有一个长度为 5 的数组（或序列）A = [a₀, a₁, a₂, a₃, a₄]：

区间 DP 需要计算所有可能子区间的最优解，例如：

• 长度为 1 的区间 (边界): [0, 0] (a₀), [1, 1] (a₁), ..., [4, 4] (a₄) → 计算 dp[0][0], dp[1][1], ..., dp[4][4]
• 长度为 3 的区间: [0, 2] (a₀, a₁, a₂), [1, 3] (a₁, a₂, a₃), [2, 4] (a₂, a₃, a₄) → 计算 dp[0][2], dp[1][3], dp[2][4] (依赖于长度 1 和 2 的区间)
• 长度为 5 的区间 (最终目标): [0, 4] (整个数组) → 计算 dp[0][4] (依赖于所有更小的区间)

计算顺序：按区间长度递增

由于 dp[i][j] 的计算依赖于比它更短的子区间（如 dp[i][k] 和 dp[k+1][j]），因此必须保证在计算 dp[i][j] 时，所有它依赖的子问题都已经被解决了。

最常用且最可靠的计算顺序是按区间长度 `len` 从小到大进行迭代：

// 假设数组/序列长度为 n (下标从 0 到 n-1 或 1 到 n)
// 这里以 1 到 n 为例
int n = /* 序列长度 */;
vector<vector<int>> dp(n + 1, vector<int>(n + 1, /* 初始化值 */));

// 1. 初始化边界条件 (长度为 1 的区间)
for (int i = 1; i <= n; ++i) {
    dp[i][i] = /* 边界值，例如 0 */;
}

// 2. 按区间长度 len 从 2 到 n 迭代
for (int len = 2; len <= n; ++len) {
    // 3. 枚举区间起点 i
    // 区间为 [i, j]，长度为 len，则 j = i + len - 1
    // i 的最大值为 n - len + 1，确保 j <= n
    for (int i = 1; i <= n - len + 1; ++i) {
        int j = i + len - 1; // 计算区间终点
        // 4. 枚举分割点 k (从 i 到 j-1)
        for (int k = i; k < j; ++k) {
            // 计算合并代价 cost(i, k, j)
            int current_cost = calculate_cost(i, k, j); // 视具体问题而定
            // 状态转移
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + current_cost); // 或 max
        }
    }
}

// 最终答案通常是 dp[1][n]

计算顺序可视化演示 (n=5)

考虑一个长度为 5 的序列，下标 1 到 5。我们将演示 DP 表格的填充顺序。

矩阵链乘法：状态定义与转移方程

我们定义状态 dp[i][j] 为：

计算矩阵子链 AᵢAᵢ₊₁...Aⱼ 的最少标量乘法次数。

我们的最终目标是求解 dp[1][n]。

↑ 考虑最后一次乘法发生在分割点 k 处

边界条件：

// 计算单个矩阵 Aᵢ 不需要乘法
dp[i][i] = 0;  // for all i from 1 to n

状态转移方程：

要计算 dp[i][j]，我们考虑所有可能的最后一次乘法发生的位置。假设最后一次乘法是将 (Aᵢ...A_k) 和 (A_k+1...Aⱼ) 的结果相乘，其中 i ≤ k < j。

此时的成本 = 计算 (Aᵢ...A_k) 的成本 + 计算 (A_k+1...Aⱼ) 的成本 + 最后一次合并的成本。

• 计算 (Aᵢ...A_k) 的最优成本是 dp[i][k]。结果是一个 p[i-1] × p[k] 的矩阵。
• 计算 (A_k+1...Aⱼ) 的最优成本是 dp[k+1][j]。结果是一个 p[k] × p[j] 的矩阵。
• 合并这两个结果矩阵需要 p[i-1] * p[k] * p[j] 次标量乘法。

我们需要尝试所有可能的分割点 k，并取最小值：

dp[i][j] = min( dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j] );
// 对所有 k 满足 i ≤ k < j

矩阵链乘法：算法演示 (p = [10, 20, 30, 40], n=3)

矩阵：A₁ (10×20), A₂ (20×30), A₃ (30×40)。我们需要计算 dp[1][3]。

DP 表格 (dp[i][j])：

矩阵链乘法：C++ 代码实现

下面是使用区间 DP 解决矩阵链乘法问题的 C++ 实现：

这个算法效率对于典型的竞赛题目（n ≤ 500 左右）是可接受的。

复杂度回顾与优化思考

时间复杂度 O(n³)

对于标准的区间 DP 问题，如矩阵链乘法、合并石子等，状态数为 O(n²)，每个状态的计算需要 O(n) 的时间（枚举分割点 k），因此总时间复杂度通常是 O(n³)。

空间复杂度 O(n²)

需要一个二维数组 dp[n][n] 来存储所有区间的解，空间复杂度为 O(n²)。

优化可能性？

对于某些特定的区间 DP 问题，可能存在优化方法：

• 四边形不等式优化： 如果状态转移函数满足四边形不等式（一种关于成本函数的性质），可以将枚举分割点 k 的过程优化到均摊 O(1)，使得总时间复杂度降至 O(n²)。典型的例子是优化版的石子合并。这是一种较高级的技巧。
• Garsia-Wachs 算法： 用于解决最优二叉搜索树（与某些区间 DP 问题相关）等问题，可以在 O(n log n) 甚至 O(n) 时间内完成。
• 数据结构优化： 在某些情况下，查找最优分割点 k 的过程可以通过线段树、单调队列等数据结构加速，但这不常见于基础区间 DP。

5.2 编程练习