区间 DP：从小区间合成大区间｜算法讲义

问题#

有 $n$ 堆石子排成一行，第 $i$ 堆有 $a_i$ 颗。每次只能合并相邻的两堆，代价等于合并后石子总数。经过 $n-1$ 次合并后只剩一堆，求最小总代价。

如果没有“只能合并相邻堆”的限制，可以每次合并最小的两堆并使用贪心；相邻限制让一个子问题天然对应原序列中的连续区间，因此需要区间 DP。

核心思想与不变量#

定义：

dp[l][r]=\text{把闭区间 }[l,r]\text{ 内的石子合成一堆的最小代价}.

最后一次操作一定把某个分割点 $k$ 两侧已经合好的两堆合并：

dp[l][r]=\min_{l\le k<r} \left(dp[l][k]+dp[k+1][r]+sum(l,r)\right).

其中 sum(l,r) 是区间总石子数。用前缀和：

prefix[i+1]=prefix[i]+a_i,\qquad sum(l,r)=prefix[r+1]-prefix[l].

单独一堆无需合并，所以 dp[l][l] = 0。长度为 len 的状态依赖两个更短区间，外层循环必须按区间长度从小到大枚举。

不变量是：开始处理长度 len 前，所有长度小于 len 的区间最优值都已经正确；因此枚举任何分割点时，两侧状态都可直接使用。

同时保存最优分割点 split[l][r]，便能递归恢复一种最优合并顺序。

复杂度#

区间数量为 $O(n^2)$ ，每个区间枚举 $O(n)$ 个分割点，所以时间为 $O(n^3)$ ，dp 与 split 的空间均为 $O(n^2)$ 。区间和通过前缀和在 $O(1)$ 时间取得；若每次循环求和，总复杂度会多出不必要的因子。

C++17 模板#

#include <functional>
#include <iostream>
#include <limits>
#include <string>
#include <vector>

using namespace std;

struct MergeResult {
    long long cost;
    string order;
};

MergeResult minimum_adjacent_merge_cost(const vector<long long>& stones) {
    int n = static_cast<int>(stones.size());
    if (n == 0) return {0, ""};

    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; ++i) prefix[i + 1] = prefix[i] + stones[i];

    vector<vector<long long>> dp(n, vector<long long>(n, 0));
    vector<vector<int>> split(n, vector<int>(n, -1));
    const long long infinity = numeric_limits<long long>::max() / 4;

    for (int length = 2; length <= n; ++length) {
        for (int left = 0; left + length <= n; ++left) {
            int right = left + length - 1;
            long long interval_sum = prefix[right + 1] - prefix[left];
            dp[left][right] = infinity;

            for (int middle = left; middle < right; ++middle) {
                long long candidate = dp[left][middle]
                                    + dp[middle + 1][right]
                                    + interval_sum;
                if (candidate < dp[left][right]) {
                    dp[left][right] = candidate;
                    split[left][right] = middle;
                }
            }
        }
    }

    function<string(int, int)> build = [&](int left, int right) -> string {
        if (left == right) return to_string(left + 1);
        int middle = split[left][right];
        return "(" + build(left, middle) + "+" + build(middle + 1, right) + ")";
    };

    return {dp[0][n - 1], build(0, n - 1)};
}

int main() {
    vector<long long> stones = {4, 5, 9};
    MergeResult answer = minimum_adjacent_merge_cost(stones);
    cout << "minimum cost = " << answer.cost << '\n';
    cout << "merge order = " << answer.order << '\n';
    return 0;
}

示例#

模板输出：

minimum cost = 27
merge order = ((1+2)+3)

先合并前两堆，代价为 $4+5=9$ ；再与第三堆合并，代价为 $9+9=18$ ，总代价 $27$ 。若先合并后两堆，则总代价为 $14+18=32$ 。

易错点#

dp[l][r] 的左右端点是否包含必须统一；模板使用 0-based 闭区间。
分割点范围是 left <= middle < right，右半区从 middle + 1 开始。
外层必须按区间长度递增，不能简单按左端点递增，否则依赖状态可能尚未计算。
合并代价中的 sum(l,r) 每次都要加入，它代表最后一次合并的代价。
dp[l][l] = 0，不是单堆石子数；单堆没有发生合并。
代价和可能很大，应使用 long long，无穷值还要留出做加法的余量。

问题#

核心思想与不变量#

复杂度#

C++17 模板#

示例#

易错点#

延伸阅读（非课程主线）#