力扣，合并石头最低成本算法题

待我称王封你为后i 2024-03-22 10:34 86阅读 0赞

1：这个题有题解，自己可以去看[力扣，合并石头][Link 1]

2：网上也有视频自己去看[视频讲解][Link 2]

3：下面我自己的一些理解

4：原需求：

![cc6866b63a9f4f2295f31ca4c10d6698.png][]

5：代码：使用贪心算法和最小堆来求解：

import java.util.PriorityQueue;
    
    public class MinimumCostToMergeStones {
        public int mergeStones(int[] stones, int K) {
            int n = stones.length;
            // 如果无法合并成一堆，则返回 -1
            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];
            }
    
            // dp[i][j][k] 表示将 i 到 j 的石头堆合并成 k 堆的最小成本
            int[][][] dp = new int[n][n][K + 1];
            PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
            // 初始化：dp[i][i][1] = 0，dp[i][i][k] = INF (k > 1)
            for (int i = 0; i < n; i++) {
                for (int k = 2; k <= K; k++) {
                    for (int j = i; j < n; j++) {
                        dp[i][j][k] = Integer.MAX_VALUE;
                    }
                }
            }
    
            // 状态转移
            for (int len = 2; len <= n; len++) {
                for (int i = 0; i + len <= n; i++) {
                    int j = i + len - 1;
                    for (int k = 2; k <= K; k++) {
                        for (int p = i; p < j; p += K - 1) {
                            dp[i][j][k] = Math.min(dp[i][j][k], dp[i][p][1] + dp[p + 1][j][k - 1]);
                        }
                    }
                    dp[i][j][1] = dp[i][j][K] + prefixSum[j + 1] - prefixSum[i];
                }
            }
    
            return dp[0][n - 1][1];
        }
    }

注释：

1.  首先判断是否可以合并成一堆：如果 (n - 1) % (K - 1) != 0，则无法合并成一堆。
2.  计算石头数量的前缀和。
3.  初始化 dp 数组：对于所有 i，dp\[i\]\[i\]\[1\] = 0，dp\[i\]\[i\]\[k\] = INF (k > 1)。
4.  状态转移：枚举区间长度 len，枚举左端点 i，计算右端点 j = i + len - 1。
5.  对于 k = 2, 3, ..., K，枚举中间点 p，计算 dp\[i\]\[j\]\[k\] = dp\[i\]\[p\]\[1\] + dp\[p + 1\]\[j\]\[k - 1\]。
6.  计算 dp\[i\]\[j\]\[1\] = dp\[i\]\[j\]\[K\] + prefixSum\[j + 1\] - prefixSum\[i\]。
7.  返回 dp\[0\]\[n - 1\]\[1\]，即将整个序列合并成一堆的最小成本

[Link 1]: https://leetcode.cn/problems/minimum-cost-to-merge-stones/
[Link 2]: https://www.bilibili.com/video/BV1Ld4y1176H/?buvid=Y0447608BF9A515F49FD9685A84FA35DF3E5&is_story_h5=false&mid=nqilz5vX4IWlFDCu1Shzzg%3D%3D&p=1&plat_id=114&share_from=ugc&share_medium=iphone&share_plat=ios&share_session_id=8115A5C2-1674-47E4-BBA0-A1B7EDA77C30&share_source=WEIXIN&share_tag=s_i&timestamp=1682435880&unique_k=GBaNOi6&up_id=1210435245
[cc6866b63a9f4f2295f31ca4c10d6698.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/6294cc3c1e444f4fb6e756e1d8ddfc8e.png