区间DP：从合并石子到分治思维

区间动态规划（区间DP）是一种在序列上“由小到大”逐步合并区间的算法。它特别适合解决一类问题：你要对一个序列进行某种合并或分割操作，每次操作只影响相邻的元素或者区间，并且你需要找到整个操作过程的最优（最小或最大）代价。就像拼积木：先拼好两块小积木，再把它们与别的积木拼在一起，最终拼成一大块。区间DP帮你找出最省力的拼法。

什么是区间DP的核心思路

区间DP的状态通常用一个区间 [i, j] 来表示，dp[i][j] 表示从第 i 个元素到第 j 个元素这个连续段上的最优解。然后我们通过枚举一个分割点 k，把大区间切成两个相邻的小区间，先分别算出小区间的最优解，再把它们合并起来，得到大区间的最优解。

这种“分而治之”的思路要求子问题之间没有重叠（其实是分治，但DP把子问题的结果存起来避免重复计算）。与普通分治不同的是，区间DP要求你先处理长度小的区间，再处理长度大的区间，也就是按区间长度从小到大来枚举。

经典例题：石子合并

问题描述

有 N 堆石子排成一排，每堆有一定数量。每次只能合并相邻的两堆石子，合并的代价是这两堆石子的重量之和。目标是：把所有石子合并成一堆，求最小的总代价。

生活中的类比

想象你有一排不同重量的糖果堆（每堆可能是5颗、3颗、8颗……），你每次只能把挨着的两堆糖果倒在一起，合并时要花的力气等于两堆糖果的总颗数（因为你要把两堆一起端起来）。你想用最少的力气把所有的糖果合并成一大袋。你会先合并哪两堆呢？这就需要区间DP来帮你规划。

状态定义

设 dp[i][j] 表示合并第 i 堆到第 j 堆（区间 [i, j]）的最小代价。
例如，dp[1][3] 表示把第1堆、第2堆、第3堆这三堆合并成一堆需要的最小力气。

边界条件

当区间内只有一堆石子时，不需要合并，代价为0：
dp[i][i] = 0。

状态转移方程

要把区间 [i, j] 合并成一堆，最后一步一定是把两个已经合并好的子堆合并在一起。这两个子堆分别对应区间 [i, k] 和 [k+1, j]（其中 i ≤ k < j）。所以：

dp[i][j] = min( dp[i][k] + dp[k+1][j] + sum[i][j] )，对每一个可能的 k

其中 sum[i][j] 表示区间 [i, j] 里所有石子堆的重量之和。因为最后合并这两个子堆时，要把它们所有的石子都端起来，代价就是它们总重量。

快速计算区间和：前缀和

为了快速得到 sum[i][j]，我们可以先计算一个前缀和数组 prefix：
prefix[0] = 0，prefix[i] 表示前 i 堆的总重量（ prefix[1] = stones[0]）。
那么 sum[i][j] = prefix[j+1] - prefix[i]。

枚举顺序：从小区间到大区间

先枚举区间长度 length 从 2 到 N，再枚举左端点 i，右端点 j = i + length - 1。然后在内层循环枚举分割点 k。这样保证计算 dp[i][j] 时，所有更小的区间（dp[i][k] 和 dp[k+1][j]）都已经算好了。

用积木理解

• 长度1的积木：已经拼好了（代价0）。
• 长度2的积木：直接合并两堆，代价就是两堆总和。
• 长度3的积木：有两种拼法——先合并左边两个再与右边合并，或者先合并右边两个再与左边合并。取代价小的那种。
• 以此类推，最后拼出整个序列。

代码实现（完整可运行）

下面这段代码实现了石子合并问题，变量名都用了简短英文单词，每行变量定义都有中文注释：

def merge_stones(stones):
    n = len(stones)                # 石子堆数
    if n == 0:
        return 0

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

    # dp数组，初始化为无穷大
    INF = float('inf')
    dp = [[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):
        for i in range(0, n - length + 1):   # 左端点 i
            j = i + length - 1               # 右端点 j
            # 尝试每个分割点 k (i <= k < j)
            for k in range(i, j):
                # 区间 [i, j] 的总重量
                total = prefix[j + 1] - prefix[i]
                cost = dp[i][k] + dp[k + 1][j] + total
                if cost < dp[i][j]:
                    dp[i][j] = cost

    return dp[0][n - 1]   # 整个区间 [0, n-1] 的最小代价

# 测试：石子重量 [4, 1, 1, 4]
stones = [4, 1, 1, 4]
print(merge_stones(stones))  # 输出 18

运行结果解释：

• 最优合并顺序：先合并中间两堆 1+1=2（代价2），得到 [4, 2, 4]；然后合并左边 4+2=6（代价6），得到 [6, 4]；最后合并 6+4=10（代价10）。总代价 = 2 + 6 + 10 = 18。

新手容易犯的错误

1. 区间端点搞混：比如把 j = i + length 写成 j = i + length - 1，导致数组越界或漏掉元素。一定要记住：长度 length 表示区间内元素个数，所以 j = i + length - 1。

2. 忘记初始化单堆代价为0：如果不初始化，默认值是无穷大，后续转移会出错。

3. 前缀和计算错误：total = prefix[j+1] - prefix[i] 是正确的，因为 prefix 的下标从0开始。如果不小心写成 prefix[j] - prefix[i-1] 会导致边界问题。

4. 枚举顺序颠倒：如果先枚举 i 再枚举 length，或者在枚举 k 时用了 k <= j 而不是 k < j，都会导致逻辑错误。必须外层是长度，内层是左端点。

5. 把区间总重量算在循环外面：有些同学把 total 计算放到 for k 循环外面，这是对的，因为 total 与 k 无关，提前算好可以提升效率。但注意别把 total 放错位置导致重复计算。

相关指引

区间DP是动态规划中的一类经典模型，学会它之后，你可以尝试解决以下类似问题：

• 括号匹配：给一串括号，问最少添加几个括号能让它合法（类似区间DP，但状态是“成为合法括号串的最小代价”）。
• 回文串分割：把一个字符串切成若干回文子串，求最少切几刀（状态 dp[i][j] 表示区间 [i,j] 至少切几刀）。
• 多边形切割：把一个凸多边形切割成三角形，求最小代价（类似石子合并，但状态转移略有不同）。
• 矩阵链乘：给定一系列矩阵，求连乘的最小乘法次数（与石子合并几乎一模一样）。

如果你对普通动态规划（如背包、最长上升子序列）还不熟悉，建议先巩固基础，区间DP是进阶内容。但一旦理解，它会成为你解决序列合并问题的利器。