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

1：这个题有题解，自己可以去看

2：网上也有视频自己去看

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

4：原需求：

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]，即将整个序列合并成一堆的最小成本