题目链接

合并石子

题目描述

有 堆石子排成一行，第 堆石子的质量为 。每次操作只能选择相邻的两堆石子进行合并，合并的代价等于这两堆石子的质量之和。合并后的新石堆质量也为两者之和，并位于原来的位置。你需要找出一种合并顺序，使得将所有石子合并成一堆的总代价最小。

输入:

  • 第一行输入一个整数 ，表示石堆数量。
  • 第二行输入 个整数 ，表示各石堆的质量。

输出:

  • 输出一个整数，表示最小的合并代价。

解题思路

这是一个典型的区间动态规划问题。我们要求解整个区间的最小代价，可以将其分解为求解所有子区间的最小代价。

  1. 状态定义:

    • 我们定义一个二维数组 ，表示将第 堆到第 堆的石子合并成一堆所需的最小代价。
    • 我们的最终目标是求解 。

  2. 状态转移:

    • 考虑如何计算 。将区间 的石子合并成一堆，其最后一步必然是将两个已经合并好的相邻子堆进行合并。这两个子堆可以是 和 ，其中 是 范围内的任意一个分割点。
    • 合并 和 这两大堆的代价是这个区间内所有石子的总质量，我们记为 。
    • 因此，形成 的总代价为：（合并[i, k]的代价） + （合并[k+1, j]的代价） + （最后一次合并的代价）。
    • 为了求得 的最小值，我们需要遍历所有可能的分割点 。
    • 状态转移方程为：

  3. 预处理:

    • 为了快速计算任意区间 [i, j] 的质量和 ，我们可以预处理一个前缀和数组 prefix_sum。
    • 。

  4. 遍历顺序:

    • 动态规划的计算依赖于比当前区间更短的子问题的解。因此，我们需要按照区间长度从小到大的顺序进行遍历。
    • 外层循环遍历区间长度 len (从2到 )。
    • 中层循环遍历区间的起始点 i。
    • 内层循环遍历分割点 k。

  5. 基本情况:

    • 当区间长度为1时，即 ，石子堆已经是一堆了，不需要合并，所以 。

代码

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

using namespace std;

const long long INF = 1e18;

int main() {
    int N;
    cin >> N;
    vector<int> w(N + 1);
    vector<long long> prefix_sum(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        cin >> w[i];
        prefix_sum[i] = prefix_sum[i - 1] + w[i];
    }

    vector<vector<long long>> dp(N + 1, vector<long long>(N + 1, 0));

    // len 是区间长度
    for (int len = 2; len <= N; ++len) {
        // i 是区间的起始点
        for (int i = 1; i <= N - len + 1; ++i) {
            int j = i + len - 1; // 区间的终点
            dp[i][j] = INF;
            long long sum_ij = prefix_sum[j] - prefix_sum[i - 1];
            // k 是分割点
            for (int k = i; k < j; ++k) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum_ij);
            }
        }
    }

    cout << dp[1][N] << "\n";
    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];
        long[] prefixSum = new long[N + 1];

        for (int i = 1; i <= N; i++) {
            w[i] = sc.nextInt();
            prefixSum[i] = prefixSum[i - 1] + w[i];
        }

        long[][] dp = new long[N + 1][N + 1];

        // len 是区间长度
        for (int len = 2; len <= N; len++) {
            // i 是区间的起始点
            for (int i = 1; i <= N - len + 1; i++) {
                int j = i + len - 1; // 区间的终点
                dp[i][j] = Long.MAX_VALUE;
                long sum_ij = prefixSum[j] - prefixSum[i - 1];
                // k 是分割点
                for (int k = i; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum_ij);
                }
            }
        }
        System.out.println(dp[1][N]);
    }
}

# 读取输入
N = int(input())
w = list(map(int, input().split()))

# 计算前缀和
prefix_sum = [0] * (N + 1)
for i in range(N):
    prefix_sum[i + 1] = prefix_sum[i] + w[i]

# dp[i][j] 表示合并区间 i 到 j 的最小代价（0-indexed）
dp = [[0] * N for _ in range(N)]

# len 是区间长度
for length in range(2, N + 1):
    # i 是区间的起始点
    for i in range(N - length + 1):
        j = i + length - 1 # 区间的终点
        dp[i][j] = float('inf')
        sum_ij = prefix_sum[j + 1] - prefix_sum[i]
        # k 是分割点
        for k in range(i, j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum_ij)

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

算法及复杂度

  • 算法：区间动态规划
  • 时间复杂度： - 三层循环分别遍历区间长度、起始点和分割点，每层循环的规模都是 。
  • 空间复杂度： - 主要开销来自存储DP状态的二维数组。