题目描述
有 N 堆石头排成一排,第 i 堆中有stones[i]块石头。
每次移动(move)需要将连续K堆石头合并为一堆,而这个移动的成本为这K堆石头的总数。
找出把所有石头合并成一堆的最低成本。如果不可能,返回 -1 。
提示:
1 <= stones.length <= 30
2 <= K <= 30
1 <= stones[i] <= 100
样例
示例 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,这是可能的最小值。
算法1
(记忆化搜索)
时间复杂度
4ms, < o(n^3 / K)
击败96.58%用户
参考文献
C++ 代码
class Solution {
public:
int f[31][31][31];
int sum[31];
int dfs(int l, int r, int group, int K) {
if (l == r) return 0;
if (f[l][r][group]) return f[l][r][group];
if (group == 1) {
if (r - l + 1 == K)
return f[l][r][1] = sum[r] - sum[l-1];
return (r - l) % (K - 1) == 0 ? dfs(l, r, K, K) + sum[r] - sum[l-1]: 0x3f3f3f3f;
}
int ans = 0x3f3f3f3f;
for (int k = l; k < r; k += (K - 1))
ans = min(ans, dfs(l, k, 1, K) + dfs(k+1, r, group - 1, K));
return f[l][r][group] = ans;
}
int mergeStones(vector<int>& stones, int K) {
int n = stones.size();
if ((n - 1) % (K - 1) != 0) {
return -1;
}
if (n < 2) return 0;
for (int i = 0; i < stones.size(); i ++){
sum[i + 1] += sum[i] + stones[i];
}
return dfs(1, n, 1, K);
}
};
老哥教教我