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

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];
    }
}

注释：