题解 | #石子合并#

题目链接

题目描述

有 $n$ 堆石子排成一行，第 $i$ 堆石子的质量为 $w_i$ 。每次操作只能选择相邻的两堆石子合并，代价等于这两堆石子的质量之和。合并后形成的新石堆质量也为两者之和，并继续与左右相邻石堆相邻。目标是找到一种合并顺序，使得将所有石子合并成一堆的总代价最小。

解题思路

这是一个典型的区间动态规划问题。我们的目标是求将所有 $n$ 堆石子合并为一堆的最小代价。

1. 状态定义

我们定义 $dp[i][j]$ 为将区间 $[i, j]$ （即从第 $i$ 堆到第 $j$ 堆）的石子合并成一堆的最小代价。我们的最终目标是求解 $dp[1][n]$ 。

2. 状态转移

对于区间 $[i, j]$ ，其最后一次合并必然是将两个已经合并好的相邻子区间合并而成的。我们可以枚举这个分割点 $k$ ，其中 $i \le k < j$ 。这意味着区间 $[i, j]$ 是由区间 $[i, k]$ 和区间 $[k+1, j]$ 合并而成的。

将区间 $[i, k]$ 合并成一堆的最小代价是 $dp[i][k]$ 。
将区间 $[k+1, j]$ 合并成一堆的最小代价是 $dp[k+1][j]$ 。
将这两堆合并的代价是它们各自的总质量之和，也就是从第 $i$ 堆到第 $j$ 堆所有石子的总质量。

为了快速计算任意区间的质量和，我们可以预处理一个前缀和数组 $s$ ，其中 $s[i] = \sum_{p=1}^{i} w_p$ 。那么区间 $[i, j]$ 的质量和就是 $s[j] - s[i-1]$ 。

综合以上分析，状态转移方程为： $dp[i][j] = \min_{i \le k < j} \{ dp[i][k] + dp[k+1][j] + (s[j] - s[i-1]) \}$

3. 初始化

当 $i=j$ 时，区间只包含一堆石子，无需合并，代价为 0。所以 $dp[i][i] = 0$ 。
对于其他 $dp[i][j]$ （其中 $i \neq j$ ），可以初始化为一个极大值。

4. 遍历顺序

为了保证计算 $dp[i][j]$ 时所依赖的子问题 $dp[i][k]$ 和 $dp[k+1][j]$ 都已经被计算过，我们需要按照区间的长度从小到大进行遍历。我们枚举区间长度 $len$ 从 2 到 $n$ ，然后枚举区间的左端点 $i$ ，右端点 $j$ 自然就是 $i + len - 1$ 。

最终的答案即为 $dp[1][n]$ 。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

const int INF = 1e9;

int main() {
    int n;
    cin >> n;

    vector<int> w(n + 1);
    vector<int> s(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
        s[i] = s[i - 1] + w[i];
    }

    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

    for (int len = 2; len <= n; ++len) {
        for (int i = 1; i <= n - len + 1; ++i) {
            int j = i + len - 1;
            dp[i][j] = INF;
            int cost = s[j] - s[i - 1];
            for (int k = i; k < j; ++k) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + cost);
            }
        }
    }

    cout << dp[1][n] << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] w = new int[n + 1];
        int[] s = new int[n + 1];
        s[0] = 0;
        for (int i = 1; i <= n; i++) {
            w[i] = sc.nextInt();
            s[i] = s[i - 1] + w[i];
        }

        int[][] dp = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            Arrays.fill(dp[i], 0);
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                int cost = s[j] - s[i - 1];
                for (int k = i; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + cost);
                }
            }
        }

        System.out.println(dp[1][n]);
    }
}

n = int(input())
w = list(map(int, input().split()))

s = [0] * (n + 1)
for i in range(n):
    s[i + 1] = s[i] + w[i]

dp = [[0] * n for _ in range(n)]

for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
        dp[i][j] = float('inf')
        cost = s[j + 1] - s[i]
        for k in range(i, j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + cost)

print(dp[0][n - 1])

算法及复杂度

算法：区间动态规划 (Interval Dynamic Programming)
时间复杂度： $\mathcal{O}(n^3)$ 。我们有三层循环：第一层枚举区间长度 $len$ (从 2 到 $n$ )，第二层枚举区间起始点 $i$ (从 1 到 $n-len+1$ )，第三层枚举分割点 $k$ (从 $i$ 到 $j-1$ )。
空间复杂度： $\mathcal{O}(n^2)$ 。我们需要一个二维数组 $dp$ 来存储状态，以及一个一维数组 $s$ 存储前缀和。