多维与区间动态规划 - NOI提高级教程

📖 算法原理：区间合并与最优子结构

区间动态规划是线性 DP 的重要扩展。它以“区间长度”为阶段，从小区间的最优解开始，通过不断合并相邻的小区间，逐步递推出大区间的最优状态。

📐 石子合并问题与区间递推状态转移

设有 $N$ 堆石子排成一排，每堆有特定的重量。每次只能合并相邻的两堆，合并的花费为两堆重量之和。求合并为一堆的最小代价。

我们用 dp[i][j] 表示将第 $i$ 堆到第 $j$ 堆石子合并为一堆的最小花费。状态转移方程为：

$$\color{cyan} dp[i][j] = \min_{i \le k < j} \{ dp[i][k] + dp[k+1][j] \} + \sum_{r=i}^{j} weight[r]$$

其物理意义为：要合并区间 $[i, j]$ 的石子，必须在某个位置 $k$ 将其劈开，先分别合并左侧 $[i, k]$ 与右侧 $[k+1, j]$ 的石子，再花最后一笔“关税”将左右两大半拧成一整堆。

演示速度：

点击"开始演示"或"单步执行"观察区间长度由 2 递增到 4 时的 DP 拼装以及矩阵变化。

i \ j	1	2	3	4

当前区间长度 L-

区间起点 I-

区间终点 J-

当前分裂决策点 K-

void intervalDP() {
    for (int len = 2; len <= n; len++) { // 1. 枚举区间长度阶段
        for (int i = 1; i <= n - len + 1; i++) { // 2. 枚举起点 i
            int j = i + len - 1; // 终点 j
            dp[i][j] = INF;
            
            // 3. 枚举中介分裂位置 k，寻找最优决策
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[i][j]);
            }
        }
    }
}

📋 区间 DP 决策历史步骤