Hard

题目描述

有 n 堆石头排成一行，第 i 堆中有 stones[i] 块石头。

每次移动需要将 恰好连续的 k 堆 石头合并为一堆，移动的成本为这 k 堆石头的总数。

返回将所有石头合并为一堆的最低成本。如果无法合并，返回 -1。

示例 1：

输入：stones = [3,2,4,1], k = 2
输出：20
解释：我们从 [3, 2, 4, 1] 开始。
我们合并 [3, 2]，成本为 5，剩下 [5, 4, 1]。
我们合并 [4, 1]，成本为 5，剩下 [5, 5]。
我们合并 [5, 5]，成本为 10，剩下 [10]。
总成本为 20，这是可能的最小值。

示例 2：

输入：stones = [3,2,4,1], k = 3
输出：-1
解释：任何合并操作后，都会剩下 2 堆，无法继续合并。所以任务不可能完成。

示例 3：

输入：stones = [3,5,1,2,6], k = 3
输出：25
解释：我们从 [3, 5, 1, 2, 6] 开始。
我们合并 [5, 1, 2]，成本为 8，剩下 [3, 8, 6]。
我们合并 [3, 8, 6]，成本为 17，剩下 [17]。
总成本为 25，这是可能的最小值。

提示：

  • n == stones.length
  • 1 <= n <= 30
  • 1 <= stones[i] <= 100
  • 2 <= k <= 30

解题思路

这是一道经典的区间动态规划问题，需要分两个阶段考虑：

第一步：判断是否能合并成一堆 每次操作将 k 堆合并成 1 堆，相当于减少了 k-1 堆。要从 n 堆合并成 1 堆，总共需要减少 n-1 堆。 因此需要满足：(n-1) % (k-1) == 0，否则返回 -1。

第二步：动态规划求最小成本 使用三维 DP：dp[i][j][m] 表示将区间 [i,j] 的石头合并成 m 堆的最小成本。

状态转移方程：

  • 当 m > 1 时：dp[i][j][m] = min(dp[i][mid][1] + dp[mid+1][j][m-1]) for all valid mid
  • 当 m == 1 时：dp[i][j][1] = dp[i][j][k] + sum(stones[i:j+1])

其中 sum(stones[i:j+1]) 表示区间 [i,j] 石头总数，可以用前缀和优化。

边界条件：

  • dp[i][i][1] = 0（单堆不需要合并成本）
  • 其他情况初始化为无穷大

最终答案为 dp[0][n-1][1]。

代码实现

class Solution {
public:
    int mergeStones(vector<int>& stones, int k) {
        int n = stones.size();
        if ((n - 1) % (k - 1) != 0) return -1;
        
        vector<int> prefixSum(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + stones[i];
        }
        
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(k + 1, INT_MAX)));
        
        for (int i = 0; i < n; i++) {
            dp[i][i][1] = 0;
        }
        
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                for (int m = 2; m <= k; m++) {
                    for (int mid = i; mid < j; mid += k - 1) {
                        if (dp[i][mid][1] != INT_MAX && dp[mid + 1][j][m - 1] != INT_MAX) {
                            dp[i][j][m] = min(dp[i][j][m], dp[i][mid][1] + dp[mid + 1][j][m - 1]);
                        }
                    }
                }
                if (dp[i][j][k] != INT_MAX) {
                    dp[i][j][1] = dp[i][j][k] + prefixSum[j + 1] - prefixSum[i];
                }
            }
        }
        
        return dp[0][n - 1][1];
    }
};

class Solution:
    def mergeStones(self, stones: List[int], k: int) -> int:
        n = len(stones)
        if (n - 1) % (k - 1) != 0:
            return -1
        
        prefix_sum = [0]
        for stone in stones:
            prefix_sum.append(prefix_sum[-1] + stone)
        
        dp = [[[float('inf')] * (k + 1) for _ in range(n)] for _ in range(n)]
        
        for i in range(n):
            dp[i][i][1] = 0
        
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                for m in range(2, k + 1):
                    mid = i
                    while mid < j:
                        if dp[i][mid][1] != float('inf') and dp[mid + 1][j][m - 1] != float('inf'):
                            dp[i][j][m] = min(dp[i][j][m], dp[i][mid][1] + dp[mid + 1][j][m - 1])
                        mid += k - 1
                
                if dp[i][j][k] != float('inf'):
                    dp[i][j][1] = dp[i][j][k] + prefix_sum[j + 1] - prefix_sum[i]
        
        return dp[0][n - 1][1]

public class Solution {
    public int MergeStones(int[] stones, int k) {
        int n = stones.Length;
        if ((n - 1) % (k - 1) != 0) return -1;
        
        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + stones[i];
        }
        
        int[,,] dp = new int[n, n, k + 1];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int m = 0; m <= k; m++) {
                    dp[i, j, m] = int.MaxValue;
                }
            }
        }
        
        for (int i = 0; i < n; i++) {
            dp[i, i, 1] = 0;
        }
        
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                for (int m = 2; m <= k; m++) {
                    for (int mid = i; mid < j; mid += k - 1) {
                        if (dp[i, mid, 1] != int.MaxValue && dp[mid + 1, j, m - 1] != int.MaxValue) {
                            dp[i, j, m] = Math.Min(dp[i, j, m], dp[i, mid, 1] + dp[mid + 1, j, m - 1]);
                        }
                    }
                }
                if (dp[i, j, k] != int.MaxValue) {
                    dp[i, j, 1] = dp[i, j, k] + prefixSum[j + 1] - prefixSum[i];
                }
            }
        }
        
        return dp[0, n - 1, 1];
    }
}

var mergeStones = function(stones, k) {
    const n = stones.length;
    if ((n - 1) % (k - 1) !== 0) return -1;
    
    const prefixSum = [0];
    for (const stone of stones) {
        prefixSum.push(prefixSum[prefixSum.length - 1] + stone);
    }
    
    const dp = Array(n).fill().map(() => 
        Array(n).fill().map(() => 
            Array(k + 1).fill(Infinity)
        )
    );
    
    for (let i = 0; i < n; i++) {
        dp[i][i][1] = 0;
    }
    
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;
            for (let m = 2; m <= k; m++) {
                for (let mid = i; mid < j; mid += k - 1) {
                    if (dp[i][mid][1] !== Infinity && dp[mid + 1][j][m - 1] !== Infinity) {
                        dp[i][j][m] = Math.min(dp[i][j][m], dp[i][mid][1] + dp[mid + 1][j][m - 1]);
                    }
                }
            }
            if (dp[i][j][k] !== Infinity) {
                dp[i][j][1] = dp[i][j][k] + prefixSum[j + 1] - prefixSum[i];
            }
        }
    }
    
    return dp[0][n - 1][1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n³ × k)
空间复杂度O(n² × k)

相关题目