合并石头的最低成本【LC1000】
有
N堆石头排成一排，第i堆中有stones[i]块石头。每次*移动（move）*需要将连续的
K堆石头合并为一堆，而这个移动的成本为这K堆石头的总数。找出把所有石头合并成一堆的最低成本。如果不可能，返回
-1。
等校车的时候用手机看了一眼，感觉是区间dp，但这几天都在练习区间dp，心里想不会那么巧吧
然后坐下来就没往区间dp想，首先先确定石头堆数和K的关系，然后想到贪心，先合并的K堆石， 在之后还会与其他石头进行合并，因此优先合并连续k堆石头最小的k堆，然后删除合并的石头，加入新合并后的，然后再进行删除，直到石头的堆数为k。然后遇到了错误的案例，上面的贪心不是最优的，然后想着那就每次枚举所有的k kk堆石头吧，然后超时了。最后放弃，看题解，emm，真的是区间dp…
递归+记忆化
- 思路
实现
class Solution { int[][][] dp; int[] sum; int k; public int mergeStones(int[] stones, int k) { int n = stones.length; if ((n - 1) % (k - 1) != 0) return -1; dp = new int[n + 1][n + 1][k + 1]; sum = new int[n + 1]; this.k = k; for (int i = 0; i <= n; i++){ for (int j = 0; j <= n; j++){ Arrays.fill(dp[i][j], -1); } } for (int i = 0; i < n; i++){ sum[i + 1] = sum[i] + stones[i]; } return dfs(0, n - 1 , 1); } public int dfs(int i, int j, int p){ if (dp[i][j][p] != -1) return dp[i][j][p]; if (p == 1){ return i == j ? 0 : dfs(i, j, k) + sum[j + 1] - sum[i]; } int res = Integer.MAX_VALUE; for (int m = i; m < j; m += k - 1){ res = Math.min(res, dfs(i, m, 1) + dfs(m + 1, j, p - 1)); } dp[i][j][p] = res; return res; } }
class Solution { private int[][] memo; private int[] s; private int k; public int mergeStones(int[] stones, int k) { int n = stones.length; if ((n - 1) % (k - 1) > 0) // 无法合并成一堆 return -1; s = new int[n + 1]; for (int i = 0; i < n; i++) s[i + 1] = s[i] + stones[i]; // 前缀和 this.k = k; memo = new int[n][n]; for (int i = 0; i < n; ++i) Arrays.fill(memo[i], -1); // -1 表示还没有计算过 return dfs(0, n - 1); } private int dfs(int i, int j) { if (i == j) return 0; // 只有一堆石头，无需合并 if (memo[i][j] != -1) return memo[i][j]; int res = Integer.MAX_VALUE; for (int m = i; m < j; m += k - 1) res = Math.min(res, dfs(i, m) + dfs(m + 1, j)); if ((j - i) % (k - 1) == 0) // 可以合并成一堆 res += s[j + 1] - s[i]; return memo[i][j] = res; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/minimum-cost-to-merge-stones/solutions/2207235/tu-jie-qu-jian-dpzhuang-tai-she-ji-yu-yo-ppv0/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
动态规划
class Solution { public int mergeStones(int[] stones, int k) { int n = stones.length; if ((n - 1) % (k - 1) > 0) // 无法合并成一堆 return -1; var s = new int[n + 1]; for (int i = 0; i < n; i++) s[i + 1] = s[i] + stones[i]; // 前缀和 var f = new int[n][n]; for (int i = n - 1; i >= 0; --i) for (int j = i + 1; j < n; ++j) { f[i][j] = Integer.MAX_VALUE; for (int m = i; m < j; m += k - 1) f[i][j] = Math.min(f[i][j], f[i][m] + f[m + 1][j]); if ((j - i) % (k - 1) == 0) // 可以合并成一堆 f[i][j] += s[j + 1] - s[i]; } return f[0][n - 1]; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/minimum-cost-to-merge-stones/solutions/2207235/tu-jie-qu-jian-dpzhuang-tai-she-ji-yu-yo-ppv0/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
