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];
}
}
注释：
- 首先判断是否可以合并成一堆：如果 (n – 1) % (K – 1) != 0，则无法合并成一堆。
- 计算石头数量的前缀和。
- 初始化 dp 数组：对于所有 i，dp[i][i][1] = 0，dp[i][i][k] = INF (k > 1)。
- 状态转移：枚举区间长度 len，枚举左端点 i，计算右端点 j = i + len – 1。
- 对于 k = 2, 3, …, K，枚举中间点 p，计算 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]。
- 返回 dp[0][n – 1][1]，即将整个序列合并成一堆的最小成本
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/160679.html
