LeetCode 1000: Minimum Cost to Merge Stones

题目链接

https://leetcode.com/problems/minimum-cost-to-merge-stones/

题意

有 N 堆石头排成一排,第 i 堆中有 stones[i] 块石头。

每次移动(move)需要将连续的 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,这是可能的最小值。

提示

  • 1 <= stones.length <= 30
  • 2 <= K <= 30
  • 1 <= stones[i] <= 100

题目类型

动态规划

题目分析

dp数组有l,r,k三维,表示l~r的石子合成k堆所需的最小代价
初始条件:
$ f[l][l][1] = 0,l = 0, 1, 2, … , n - 1 $ 其余取 INF
最终答案:
$f[0][n - 1][1]$
转移方程:
$f[l][r][k] = min(f[l][r][k], f[l][m][1] + f[m + 1][r][k - 1]),m = l, l + K - 1, l + 2 * K - 2…$
$f[l][r][1] = f[l][r][K] + sum(stones[l] … stones[r])$(P.S.此处的K是题目中的大K)
具体看代码实现,一看就懂

时间复杂度

$O(N ^ {2} \ast K)$

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const int INF = 1e9;
class Solution {
private:
vector<int>S;
public:
int get_sum(int l, int r) {
if (l > r)
return 0;
return S[r + 1] - S[l];
}
int mergeStones(vector<int>& stones, int K) {
int n = stones.size();
int i, l, k, r, m;
if ((n - 1) % (K - 1) != 0)
return -1;
S.clear();
S.push_back(0);
for (i = 0; i < n; i++)
S.push_back(S[S.size() - 1] + stones[i]);
vector<vector<vector<int>>> f(n, vector<vector<int>>(n, vector<int>(K + 1, INF)));
for (l = 0; l < n; l++)
f[l][l][1] = 0;
for (i = 2; i <= n; i++) {
for (l = 0; l + i - 1 < n; l++) {
r = l + i - 1;
for (k = 2; k <= K; k++) {
for (m = l; m < r; m += K - 1)
f[l][r][k] = min(f[l][r][k], f[l][m][1] + f[m + 1][r][k - 1]);
}
f[l][r][1] = f[l][r][K] + get_sum(l, r);
}
}
return f[0][n - 1][1];
}
};
0%