一、定义

区间DP是动态规划的一种特殊形式，主要用于解决涉及区间操作的问题，比如合并区间、分割区间、区间匹配等。

其核心思想是通过枚举区间的划分点，将大区间的问题分解为小区间的子问题，逐步求解并保存中间结果。

二、基本特征

• 问题定义：通常涉及一个序列或区间，如数组、字符串等。

• 状态表示：一般用 dp[i][j] 表示区间 [i, j] 的最优解。

• 转移方程：通过枚举区间内的某个分割点 k，将 [i, j] 拆分为 [i, k] 和 [k+1, j]，然后合并子问题的解。

• 初始化：通常 dp[i][i] 表示单个元素的最优解（如 dp[i][i] = 0 或 dp[i][i] = cost[i]）。

• 遍历顺序：一般采用区间长度从小到大的顺序计算，确保子问题先被求解。

三、区间DP模板

for (int len = 1; len <= n; len++) {          // 枚举区间长度
    for (int i = 0; i + len - 1 < n; i++) {   // 枚举起点i
        int j = i + len - 1;                  // 计算终点j
        if (len == 1) {                       // 初始化
            dp[i][j] = ...;
            continue;
        }
        for (int k = i; k < j; k++) {         // 枚举分割点k
            dp[i][j] = min/max(dp[i][j], dp[i][k] + dp[k+1][j] + cost);
        }
    }
}

四、例题：石子合并

题目：【题解】石子合并 - 青少年编程知识记录

问题描述：有 n 堆石子排成一排，每次只能合并相邻的两堆，合并的代价是两堆石子的总数。求将所有石子合并成一堆的最小总代价。

输入: stones = [3, 1, 2, 4]
输出: 20
解释:
1. 合并 [1, 2] → 代价=3, 剩余 [3, 3, 4]
2. 合并 [3, 3] → 代价=6, 剩余 [6, 4]
3. 合并 [6, 4] → 代价=10, 总代价=3+6+10=19

(1) 状态定义

• dp[i][j]：表示合并区间 [i, j] 的所有石子堆的最小总代价。

• 初始化：

• 如果 i == j（即区间长度为1），dp[i][j] = 0（因为不需要合并）。

• 否则 dp[i][j] = +∞（初始化为极大值，方便后续取最小值）。

(2) 状态转移方程

• 对于区间 [i, j]，枚举所有可能的分割点 k（i ≤ k < j），将其分成两个子区间：

• [i, k] 和 [k+1, j]。

• 合并这两个子区间的总代价是：

• dp[i][k]（合并 [i, k] 的代价）

• dp[k+1][j]（合并 [k+1, j] 的代价）

• sum(i, j)（当前合并的代价，即区间 [i, j] 的石子总重量）。

• 因此，状态转移方程为：

  $$dp[i][j]=\underset{i\le k<j}{\min }(dp[i][k]+dp[k+1][j]+\text{sum}(i,j))$$

(3) 计算顺序

• 按区间长度从小到大计算：

• 先计算所有长度为2的区间，再计算长度为3的区间，依此类推，直到计算整个区间 [0, n-1]。

• 前缀和优化：

• 为了快速计算 sum(i, j)，可以预先计算前缀和数组 prefix：

  $$\text{sum}(i,j)=\text{prefix}[j+1]-\text{prefix}[i]$$

过程解释：

（注意分割点K）

(1) 初始化

• 石子数组：[3, 1, 2, 4]，n = 4。

• 前缀和 prefix：

• prefix[0] = 0

• prefix[1] = 3

• prefix[2] = 3 + 1 = 4

• prefix[3] = 4 + 2 = 6

• prefix[4] = 6 + 4 = 10

• dp 表初始化为 ∞，对角线 dp[i][i] = 0：

(2) 计算长度为2的区间

• 区间 [0, 1]：

• dp[0][0] + dp[1][1] + sum(0,1) = 0 + 0 + (prefix[2]-prefix[0]) = 4

• 分割点 k = 0：

• dp[0][1] = 4

• 区间 [1, 2]：

• dp[1][1] + dp[2][2] + sum(1,2) = 0 + 0 + (prefix[3]-prefix[1]) = 3

• 分割点 k = 1：

• dp[1][2] = 3

• 区间 [2, 3]：

• dp[2][2] + dp[3][3] + sum(2,3) = 0 + 0 + (prefix[4]-prefix[2]) = 6

• 分割点 k = 2：

• dp[2][3] = 6

更新后的 dp 表：

(3) 计算长度为3的区间

• 区间 [0, 2]：

• dp[0][1] + dp[2][2] + sum(0,2) = 4 + 0 + 6 = 10

• dp[0][0] + dp[1][2] + sum(0,2) = 0 + 3 + (prefix[3]-prefix[0]) = 9

• 分割点 k = 0：

• 分割点 k = 1：

• dp[0][2] = min(9, 10) = 9

• 区间 [1, 3]：

• dp[1][2] + dp[3][3] + sum(1,3) = 3 + 0 + 7 = 10

• dp[1][1] + dp[2][3] + sum(1,3) = 0 + 6 + (prefix[4]-prefix[1]) = 13

• 分割点 k = 1：

• 分割点 k = 2：

• dp[1][3] = min(13, 10) = 10

更新后的 dp 表：

(4) 计算长度为4的区间（最终结果）

• 区间 [0, 3]：

• dp[0][2] + dp[3][3] + sum(0,3) = 9 + 0 + 10 = 19

• dp[0][1] + dp[2][3] + sum(0,3) = 4 + 6 + 10 = 20

• dp[0][0] + dp[1][3] + sum(0,3) = 0 + 10 + (prefix[4]-prefix[0]) = 20

• 分割点 k = 0：

• 分割点 k = 1：

• 分割点 k = 2：

• dp[0][3] = min(20, 20, 19) = 19

最终 dp 表：

最小总代价：dp[0][3] = 19。