区间DP——从小区间一步步拼出大答案 - 七级

区间DP——像搭积木一样拼出答案

你有没有玩过搭积木？先拼好小块的房子，再把它们拼成更大的城堡。区间动态规划（区间DP） 就是这种思路：先解决小区间的问题，再一步步扩大，最终得到整个大区间的最优解。它专门用来处理那些和区间顺序有关、大问题可以拆成相邻的小区间的问题。比如：合并一堆石子求最小代价、括号匹配、回文子串分割等。

生活中的例子：合唱分组

班级要举办合唱比赛，有 n 位同学站成一排。老师想把他们分成几个连续的小组（比如第1~~3人一组，第4~~5人一组……），每个小组有一个“默契度”值——人数越多默契度越低。老师希望找到一种分组方式，使得所有小组默契度之和最大。

如果能先算好每个同学单独一组的默契度（小区间），再算两人一组，三人一组…… 是不是就能一步步推出整个队伍的默契度最大值？
这就是区间DP的典型应用：先处理长度为1的区间，再处理长度为2的，直到长度为n。

核心概念：状态、转移、遍历顺序

1. 状态定义
我们用 dp[i][j] 表示区间 [i, j]（从第 i 到第 j 个元素）的最优值。例如在合唱分组中，dp[i][j] 表示第 i 到 j 位同学这一段的最高默契度之和。

2. 状态转移
大区间 [i, j] 怎么由小区间得到？
在 i 和 j 之间找一个分割点 k（i ≤ k < j），将区间分成 [i, k] 和 [k+1, j] 两个相邻的子区间。
那么 dp[i][j] 就可以用这两个子区间的最优值，再加上合并这两个子区间的代价（或者收益）来计算。
公式（以“求最小值”为例）：

dp[i][j] = min( dp[i][k] + dp[k+1][j] + 合并成本 )

合并成本可能是两堆石子的重量和，也可能是两个小组的默契度乘积等。

3. 遍历顺序
先枚举区间长度，再枚举起点。

长度从 2 到 n（因为长度为1的区间已经初始化好了）
对于每个长度，枚举起点 i，计算终点 j = i + length - 1
然后在 i 和 j 之间枚举分割点 k

为什么要这样？因为计算 dp[i][j] 时，需要的子区间 dp[i][k] 和 dp[k+1][j] 的长度一定小于 length，所以先算小的长度，再算大的长度，保证子问题已经算好。

4. 初始化
长度为1的区间：dp[i][i] 通常设为0（自己合并自己代价为0），或者设为单元素的价值。

经典例子：石子合并的详细讲解

有 n 堆石子排成一排，每次只能合并相邻的两堆，合并的代价是两堆石子重量之和。问把所有石子合并成一堆的最小总代价。

为什么要用区间DP？

每次合并相邻的两堆，相当于把一段区间分成左右两段，先合并左段，再合并右段，最后把左右两段合并。
小区间合并的代价已知，大区间由小区间加当前合并代价得到。

关键工具：前缀和
为了快速计算任意区间 [i, j] 内石子的总重量，我们使用前缀和数组 prefix，其中 prefix[k] 表示前 k 堆石子的总重量。那么区间 [i, j] 的重量和 = prefix[j+1] - prefix[i]。

逐步看代码

def stone_merge(stones):
    n = len(stones)
    # 前缀和数组，长度 n+1，prefix[0]=0
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + stones[i]  # 计算前缀和

    # dp[i][j] 表示合并 i 到 j 堆的最小代价，初始化为无穷大
    dp = [[float('inf')] * n for _ in range(n)]

    # 初始化：长度为1的区间代价为0
    for i in range(n):
        dp[i][i] = 0

    # 枚举区间长度，从2开始
    for length in range(2, n+1):
        # 枚举起点 i
        for i in range(0, n - length + 1):
            j = i + length - 1  # 终点
            # 枚举分割点 k
            for k in range(i, j):
                # 合并代价 = dp[i][k] + dp[k+1][j] + 区间总重量
                cost = dp[i][k] + dp[k+1][j] + (prefix[j+1] - prefix[i])
                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n-1]

# 测试
print(stone_merge([4, 1, 1, 4]))  # 输出18

手动推演一下样例：石子堆 [4, 1, 1, 4]

长度1：dp[0][0]=0, dp[1][1]=0, dp[2][2]=0, dp[3][3]=0
长度2：
- dp[0][1]：只有一种合并方式，代价 = 0+0 + (4+1)=5
- dp[1][2]：代价 = 0+0 + (1+1)=2
- dp[2][3]：代价 = 0+0 + (1+4)=5
长度3：
- dp[0][2]：两种分法
  - k=0: dp[0][0]+dp[1][2] + 总重(4+1+1)=0+2+6=8
  - k=1: dp[0][1]+dp[2][2] + 总重6 = 5+0+6=11 → 取最小8
- dp[1][3]：同样得 min(2+0+6, 0+5+6)=8
长度4：dp[0][3]
- k=0: 0+8 + (4+1+1+4)=8+10=18
- k=1: 5+5 +10=20
- k=2: 8+0+10=18
  最小18。

新手容易犯的错误

错误1：忘记初始化
dp[i][i] 必须设为0（或其他合理值），否则大区间计算时会加上无穷大。

错误2：遍历顺序搞反
如果先枚举起点再枚举长度，计算大区间时用的小区间可能还没算好。一定要先长度、再起点。

错误3：边界条件写错
比如 j = i + length - 1，容易写成 i + length，导致数组越界。注意终点索引要小于n。

错误4：合并成本计算错误
在石子合并中，合并两堆的代价是两堆的总重量，而不是单堆重量。所以要用前缀和快速求区间和。

检查方法：写一个简单的测试用例（比如n=2或3），用手算验证代码输出是否正确。

完整可运行代码（含多组测试）

def stone_merge(stones):
    """
    石子合并：求最小总代价
    stones: 列表，每堆石子的重量
    返回：最小总代价
    """
    n = len(stones)
    if n == 1:
        return 0  # 只有一堆，不需要合并

    # 前缀和，方便计算任意区间的重量和
    prefix = [0] * (n + 1)           # 长度n+1，prefix[0]=0
    for i in range(n):
        prefix[i+1] = prefix[i] + stones[i]  # 计算前缀和

    # dp[i][j]初始化为一个大数（无穷大）
    dp = [[float('inf')] * n for _ in range(n)]

    # 自己合并自己代价为0
    for i in range(n):
        dp[i][i] = 0

    # 区间长度len从2到n
    for length in range(2, n+1):
        # 起点i从0到n-length
        for i in range(0, n - length + 1):
            j = i + length - 1       # 终点
            # 尝试每一个分割点k，k从i到j-1
            for k in range(i, j):
                # 当前合并代价 = 左区间代价 + 右区间代价 + 本区间总重量
                cur_cost = dp[i][k] + dp[k+1][j] + (prefix[j+1] - prefix[i])
                dp[i][j] = min(dp[i][j], cur_cost)

    return dp[0][n-1]

# 测试多个例子
print("样例1:", stone_merge([4, 1, 1, 4]))      # 输出18
print("样例2:", stone_merge([1, 2, 3]))         # 输出9? 手动算：先合1+2=3（代价3），再合3+3=6（代价6），总9
print("样例3:", stone_merge([5]))               # 只有一堆，输出0
print("样例4:", stone_merge([3, 2, 4, 1]))      # 可以自己验证

还有哪些问题可以用区间DP？

除了石子合并，你还能见到：

括号匹配：给一串括号，问最少添加多少个括号能让它完全匹配。dp[i][j] 表示从i到j的字符串最少添加数，转移时考虑 s[i] 和 s[j] 是否匹配。
回文子串分割：把一个字符串切割成若干回文子串，求最少切割次数。dp[i][j] 表示从i到j是否为回文，再枚举分割点。
矩阵链乘：给一系列矩阵，求最小的乘法次数。其实就是石子合并的变形——合并代价是矩阵乘法次数。

思考题：如果把上面合唱分组问题中的“默契度”设计成一个公式，比如队伍人数越多，默契度= 100 / 人数（取整），那么区间DP可以怎么定义 dp[i][j] 和转移？

掌握了区间DP，你会发现很多“合并相邻区间”的问题都可以用同样的三步法解决：

定义 dp[i][j]
枚举分割点，写出转移方程
按区间长度从小到大的顺序计算

下次遇到这样的题目，先画个区间图，从最小的积木开始搭吧！