区间DP——把大问题切成小段来思考

你有没有玩过拼图？一块大拼图很难一下子完成，但如果我们先拼好一小块（比如左上角），再拼另一小块，最后把几小块拼在一起，就轻松多了！区间DP（区间动态规划）也是这个思路：把一个大的区间问题，先拆成许多小的区间来求解，再慢慢合并成整个大区间的最优解。

咱们用一道经典题目——“石子合并”来学会这个技巧。

什么是区间DP？

想象你面前有一排石子堆，每堆有不同的重量（比如4千克、1千克、1千克、5千克）。你想把所有石子合并成一堆，但规则很特别：每次只能把相邻的两堆合并，花费的力气等于这两堆石子的总重量。比如你把[4]和[1]合并，花费4+1=5。现在的顺序就会变成[5, 1, 5]（注意原来的[4,1]变成了[5]）。问：怎样安排合并顺序，才能让总花费（力气）最少？

这个问题如果用暴力方法，把所有可能的合并顺序都试一遍，那会非常非常慢（比学校的大课间排队还慢！）。但区间DP却能高效解决它。

关键想法：无论你怎么合并，最后一步一定是把左半部分和右半部分合在一起。比如整个区间是[0,3]，最后一步可能是把左半段[0,1]和右半段[2,3]合并，也可能是[0,2]和[3]合并……但无论哪种，左半段和右半段内部的合并都要已经是最优的。所以我们只需要先算出所有小区间的最优代价，再用它们拼出大区间的最优代价。

核心步骤：状态定义、转移方程、前缀和

1. 定义状态：dp[i][j]

我们用 dp[i][j] 表示合并从第 i 堆到第 j 堆（两头都算）的最小花费。注意：数组下标从0开始，dp[0][0] 就只有一堆石子，不需要合并，代价为0。

2. 转移方程

假设我们想合并区间 [i, j]，它的长度至少是2（因为长度为1时不需要合并）。我们可以在中间找一个分割点 k，先把 [i, k] 合并成一堆，再把 [k+1, j] 合并成一堆，最后把这两堆合起来。合并这两堆的代价就是它们各自的重量之和，也就是区间 [i, j] 内所有石子的总重量。

所以：

dp[i][j] = min( dp[i][k] + dp[k+1][j] + sum(i, j) )  ，其中 k 从 i 到 j-1

这里的 sum(i, j) 是第 i 堆到第 j 堆的总重量。为什么加上它？因为最后一步合并这两大堆时，你要搬动这两个大堆的所有石子，花费就是它们的总重量。

3. 快速求区间总重量——前缀和

如果每次都重新加一遍 stones[i] + stones[i+1] + ... + stones[j]，那会很慢。我们可以提前算好前缀和数组 pre，其中 pre[t] 表示前 t 堆石子的总重量（下标从0开始）。那么 sum(i, j) = pre[j+1] - pre[i]。

举个例子：stones = [4, 1, 1, 5]

• pre[0] = 0
• pre[1] = 4
• pre[2] = 5
• pre[3] = 6
• pre[4] = 11

那么区间[1,3]（对应重量1,1,5）的总和 = pre[4] - pre[1] = 11 - 4 = 7，正确。

4. 枚举顺序：先小后大

我们要先算出所有长度为1的区间（代价为0，直接初始化），然后长度2、长度3……一直算到整个区间。代码中通常用 len 表示当前区间长度，从2开始（注意长度=1已经处理好了），i 是区间起点，j = i + len - 1 是终点。

生活中的例子：合并糖果

假设你买了5颗不同口味的糖果排成一排，重量分别是：3, 2, 5, 1, 4。现在你想把它们全部合并成一个大糖球，每次只能把相邻的两颗糖捏在一起，力气等于它们的重量之和。问最少需要多少力气？

用区间DP：先考虑区间[0,0]（只有第0颗）花费0，区间[1,1]花费0……然后算长度为2的区间，比如[0,1]：它只能通过直接合并（k=0）得到，代价=0+0+(3+2)=5。长度为3的区间[0,2]：可以分割成[0,0]+[1,2]或[0,1]+[2,2]，分别计算并取最小值。逐步计算，最后得到整个区间[0,4]的最小合并代价。

常见错误（新手最容易踩的坑）

1. 忘记初始化 dp[i][j] 为一个大数

在枚举分割点求最小值时，dp[i][j] 必须一开始设为一个很大的值（比如 INT_MAX），否则它默认是0，那么所有更小的候选项都不会更新，答案就变成0了。

2. 分割点循环边界写错

k 必须从 i 到 j-1，不能写成 k <= j。因为如果 k=j，那么右半段 [k+1, j] 就成了 [j+1, j]，这是不合法的空区间。记住：分割点必须把区间分成两个非空的部分。

3. 区间长度枚举顺序不对

有人可能会先枚举起点 i，再枚举终点 j，这样会漏掉小区间还没算完的情况。必须先枚举长度，再枚举起点，保证所有更短的区间都已经计算好了。

4. 前缀和数组大小

前缀和数组 pre 的长度是 n+1，因为 pre[0]=0，pre[n] 是总和。计算 sum(i,j) 时用 pre[j+1] - pre[i]，注意下标不要越界。

完整可运行的代码示例

下面是用 C++ 写的完整的石子合并程序，你可以直接复制到你的电脑上跑一跑。

#include <iostream>
#include <vector>
#include <climits>   // 用于 INT_MAX
using namespace std;

int main() {
    // 石子重量数组，你可以改成其他数字试试
    vector<int> stones = {4, 1, 1, 5};   // 每堆石子的重量
    int n = stones.size();               // 堆数

    // 计算前缀和，方便后续求区间总重量
    vector<int> pre(n + 1, 0);           // pre[i] = stones[0]到stones[i-1]的总和
    for (int i = 0; i < n; i++) {
        pre[i + 1] = pre[i] + stones[i]; // 比如 pre[1] = stones[0]
    }

    // 初始化dp数组，所有dp[i][i] = 0 （只有一堆，不需要合并）
    vector<vector<int>> dp(n, vector<int>(n, 0));

    // 枚举区间长度，从2开始（长度为1已经初始化好了）
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {    // 起点 i
            int j = i + len - 1;                   // 终点 j
            dp[i][j] = INT_MAX;                    // 先设为一个很大的数
            // 枚举分割点 k，从 i 到 j-1
            for (int k = i; k < j; k++) {
                // 左半段代价 + 右半段代价 + 合并这两大堆的代价（即区间总重）
                int cost = dp[i][k] + dp[k + 1][j] + (pre[j + 1] - pre[i]);
                if (cost < dp[i][j]) {
                    dp[i][j] = cost;   // 更新为更小的代价
                }
            }
        }
    }

    // 输出结果：合并整个区间的最小代价
    cout << "最小合并代价: " << dp[0][n - 1] << endl;

    return 0;
}

运行这段代码，你会看到输出：

最小合并代价: 17

你可以自己用手算一算，看看是不是17。

相关指引

学会了区间DP，你还可以用它解决很多类似的问题，比如：

• 括号匹配：给定一串括号（比如 (()(()))），问最少添加多少个括号能让它完全匹配。思路是用 dp[i][j] 表示区间 [i, j] 的最小添加数，再根据两端的字符决定能不能直接匹配。
• 回文串分割：把一个字符串切成若干段，使得每段都是回文串，问最少切几次。也可以用区间DP，先预处理哪些子串是回文，再转移。
• 合并果子（石子合并的变种）：如果不要求相邻合并，而是可以任意合并两堆，那就变成了贪心（哈夫曼树）。但如果是相邻合并，就必须用区间DP。

记住区间DP的口诀：“先看小，再看大，分割点挨个试”，你也能轻松掌握！快去用你最喜欢的代码试一试吧。