LeetCode 1000. 合并石头的最低成本

Categories:

题目描述
思路分析
1. 解法一：区间 DP（推荐）
相似题目

题目描述

✅ 1000. 合并石头的最低成本

思路分析

解法一：区间 DP（推荐）

核心思路：

若 (n - 1) % (k - 1) != 0 则无法合并为一堆，直接返回 -1。

dp[i][j] 表示将区间 [i, j] 合并为尽可能少堆的最小成本。

枚举分割点 m，按 k-1 步长转移，只有当区间长度满足可合成一堆时再加上区间和。

复杂度分析：

时间复杂度：O(n^3 / k)，其中 n 表示石头堆数量。

空间复杂度：O(n^2)，用于 DP 表。

class Solution {
    public int mergeStones(int[] stones, int k) {
        int n = stones.length;
        if ((n - 1) % (k - 1) != 0) {
            return -1;
        }

        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + stones[i];
        }

        int[][] dp = new int[n][n];
        for (int len = k; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE / 2;

                for (int m = i; m < j; m += k - 1) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m + 1][j]);
                }

                if ((len - 1) % (k - 1) == 0) {
                    dp[i][j] += prefix[j + 1] - prefix[i];
                }
            }
        }

        return dp[0][n - 1];
    }
}

func mergeStones(stones []int, k int) int {
	n := len(stones)
	if (n-1)%(k-1) != 0 {
		return -1
	}

	prefix := make([]int, n+1)
	for i := 0; i < n; i++ {
		prefix[i+1] = prefix[i] + stones[i]
	}

	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
	}

	const inf = int(1 << 60)
	for length := k; length <= n; length++ {
		for i := 0; i+length-1 < n; i++ {
			j := i + length - 1
			dp[i][j] = inf

			for m := i; m < j; m += k - 1 {
				val := dp[i][m] + dp[m+1][j]
				if val < dp[i][j] {
					dp[i][j] = val
				}
			}

			if (length-1)%(k-1) == 0 {
				dp[i][j] += prefix[j+1] - prefix[i]
			}
		}
	}

	return dp[0][n-1]
}

相似题目

题目	难度	考察点
312. 戳气球	困难	区间 DP
1039. 多边形三角剖分的最低得分	中等	区间 DP
1547. 切棍子的最小成本	困难	区间 DP
1130. 叶值的最小代价生成树	中等	区间/单调栈
1312. 让字符串成为回文串的最少插入次数	困难	区间 DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/26804473