1000 合并石头的最低成本（区间DP）（前缀和）（灵神笔记）

本文主要是介绍1000 合并石头的最低成本（区间DP）（前缀和）（灵神笔记），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

合并石头的最低成本
有 n 堆石头排成一排，第 i 堆中有 stones[i] 块石头。

每次移动需要将连续的 k 堆石头合并为一堆，而这次移动的成本为这 k 堆中石头的总数。

返回把所有石头合并成一堆的最低成本。如果无法合并成一堆，返回 -1 。

示例 1：

输入：stones = [3,2,4,1], K = 2
输出：20
解释：
从 [3, 2, 4, 1] 开始。
合并 [3, 2]，成本为 5，剩下 [5, 4, 1]。
合并 [4, 1]，成本为 5，剩下 [5, 5]。
合并 [5, 5]，成本为 10，剩下 [10]。
总成本 20，这是可能的最小值。
示例 2：

输入：stones = [3,2,4,1], K = 3
输出：-1
解释：任何合并操作后，都会剩下 2 堆，我们无法再进行合并。所以这项任务是不可能完成的。.
示例 3：

输入：stones = [3,5,1,2,6], K = 3
输出：25
解释：
从 [3, 5, 1, 2, 6] 开始。
合并 [5, 1, 2]，成本为 8，剩下 [3, 8, 6]。
合并 [3, 8, 6]，成本为 17，剩下 [17]。
总成本 25，这是可能的最小值。

提示：

n == stones.length
1 <= n <= 30
1 <= stones[i] <= 100
2 <= k <= 30

题解

记忆化搜索

class Solution {private int[][] cache;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;cache = new int[n][n];for (int i = 0; i < n; i++) {Arrays.fill(cache[i], -1);}return dfs(0, n - 1);}private int dfs(int i, int j) {if (i == j) {return 0; // 只有一堆石头}if (cache[i][j] != -1) {return cache[i][j];}int ans = Integer.MAX_VALUE;for (int m = i; m < j; m += k - 1) {ans = Math.min(ans, dfs(i, m) + dfs(m + 1, j));}if ((j - i) % (k - 1) == 0) {ans += s[j + 1] - s[i]; // 可以合并成一堆}return cache[i][j] = ans;}
}

递推

class Solution {public int mergeStones(int[] stones, int k) {int n = stones.length;if ((n - 1) % (k - 1) > 0) {// 无法合并成一堆return -1;}int[] s = new int[n + 1];for (int i = 0; i < n; i++) {// 计算前缀和s[i + 1] = s[i] + stones[i];}int[][] 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];}
}