合并石子

形式化题目

给定一个长度为 $N$ 的正整数序列 $a_1, a_2, \dots, a_N$ 。每次操作只能选择序列中相邻的两个数合并成一个新数，合并得分等于这两个数之和。要求通过恰好 $N-1$ 次操作把整个序列合并成一个数，并最小化总得分。

正解

思路

如果直接枚举所有合并顺序，合法顺序的数量是卡特兰数 $C_{N-1}$ ， $N$ 达到 $100$ 时完全不可行。但注意到一个关键事实：无论怎么合并，每次操作后形成的连续段始终是原序列的一个连续子区间。因此，我们只需要关心“把某个区间 $[l, r]$ 合并成一堆的最小得分”，而不需要记录区间内部的全部历史。

设 $dp[l][r]$ 表示把第 $l$ 到第 $r$ 堆石子合并成一堆的最小得分。区间 $[l, r]$ 的最后一次合并一定发生在某个位置 $k$ （ $l \leqslant k < r$ ），把区间分成 $[l, k]$ 和 $[k+1, r]$ 两段。于是：

dp[l][r] = \min_{l \leqslant k < r} \bigl( dp[l][k] + dp[k+1][r] \bigr) + (s_r - s_{l-1})

其中 $s_i = a_1 + a_2 + \dots + a_i$ 是前缀和， $s_r - s_{l-1}$ 就是本次合并产生的得分。边界为 $dp[l][l] = 0$ ，最终答案是 $dp[1][N]$ 。

样例 DP 表

下面以样例 13 7 8 16 21 4 18 展示部分 DP 表（ $dp[l][r]$ 的值， $l$ 为行、 $r$ 为列）。

l\r	1	2	3	4	5	6	7
1	0	20	43	87	145	178	239
2		0	15	46	98	127	185
3			0	24	69	98	156
4				0	37	66	118
5					0	25	65
6						0	22
7							0

表中第 1 行第 7 列的 $239$ 就是最终答案。观察表中任意一格 $dp[l][r]$ ，它的值都来自某个分割点 $k$ ，即 $dp[l][k] + dp[k+1][r]$ 加上区间和。按区间长度从小到大填表，可以保证计算每个状态时所依赖的子区间已经算完。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 02:51
# update_at: 2026-09-30 02:51

import sys
from functools import cache

INF = 10 ** 18  # 比任何可能答案都大


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    a = [next(data) for _ in range(n)]

    # 前缀和：s[i] 表示前 i 堆石子总数，s[0] = 0。
    s = [0] * (n + 1)
    for i, x in enumerate(a, 1):
        s[i] = s[i - 1] + x

    @cache
    def dfs(l: int, r: int) -> int:
        """把第 l 到第 r 堆石子合并成一堆的最小得分，区间为 1-based 闭区间。"""
        if l == r:
            return 0
        return min(dfs(l, k) + dfs(k + 1, r) for k in range(l, r)) + s[r] - s[l - 1]

    print(dfs(1, n))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-04 23:42
 * update_at: 2026-10-04 23:42
 */

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 105;
const ll INF = 1000000000000000000LL;

ll n;
ll a[MAXN];         // a[i] 表示第 i 堆石子的数量
ll s[MAXN];         // s[i] = 前 i 堆石子的总数（前缀和），用于 O(1) 求区间和
ll dp[MAXN][MAXN];  // dp[l][r] 表示把第 l 到第 r 堆石子合并成一堆的最小得分

void read_input() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
}

void solve() {
    // 按区间长度从小到大递推，计算 dp[l][r] 时它依赖的子区间都已经算好。
    // 长度为 1 的区间不需要合并，dp[l][l] 由全局数组默认为 0。
    for (ll len = 2; len <= n; len++) {
        for (ll l = 1; l + len - 1 <= n; l++) {
            ll r = l + len - 1;
            dp[l][r] = INF;
            // 枚举最后一次合并的分割点 k，把区间 [l, r] 分成 [l, k] 与 [k+1, r] 两堆。
            for (ll k = l; k < r; k++) {
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
            }
            // 最后一次合并的得分就是整个区间的石子总数。
            dp[l][r] += s[r] - s[l - 1];
        }
    }
    cout << dp[1][n] << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

状态数： $O(N^2)$ 。
每个状态枚举分割点 $k$ ： $O(N)$ 。
时间复杂度： $O(N^3)$ 。当 $N \leqslant 100$ 时约为 $10^6$ 次运算。
空间复杂度： $O(N^2)$ ，用于 DP 表和前缀和数组。

总结

合并石子是一道经典的区间 DP 模板题。核心观察是：任何合并过程的中间状态都对应原序列的一个连续子区间，因此可以用 $dp[l][r]$ 表示区间合并的最小得分，通过枚举最后一次合并位置完成转移。实现上用前缀和加速区间求和，按区间长度从小到大递推即可。

目录

形式化题目

正解

思路

样例 DP 表

代码

复杂度

总结