个人网站的制作实验报告,服务器空间租赁,提高网站速度,宜兴网站开发题目
合并石头的最低成本 有 n 堆石头排成一排#xff0c;第 i 堆中有 stones[i] 块石头。
每次 移动 需要将 连续的 k 堆石头合并为一堆#xff0c;而这次移动的成本为这 k 堆中石头的总数。
返回把所有石头合并成一堆的最低成本。如果无法合并成一堆#xff0c;返回 -1…题目
合并石头的最低成本 有 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];}
}
