题目链接
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 | const int INF = 1e9; |