1000. Minimum Cost to Merge Stones¶
题目信息¶
- 题号:
1000
- 难度:
Hard
- 主题:
连续石堆、固定数量合并、最小费用
- 原题:
- 重点:
每次必须选择恰好
k个连续石堆合并为一堆,费用为这些石堆的石子总数;目标是最终只剩一堆,不可行时返回-1
题目重述¶
给定从左到右排列的石堆数组 stones,stones[i] 表示第 i 堆石子的数量。一次操作必须选择当前序列中恰好 k 个连续石堆,把它们合并成一堆;新石堆的石子数为所选各堆之和,本次操作费用也等于这个和。
反复执行操作,目标是最终把所有石堆合并成一堆。请返回能够达到目标的最小总费用;若由于石堆数量变化无法最终剩下一堆,返回 -1。
1 <= stones.length <= 30,1 <= stones[i] <= 100,2 <= k <= 30。
自建示例¶
先合并前三堆得到最小费用:
输入:stones = [1,2,3,4,5], k = 3
输出:21
解释:先合并 [1,2,3],费用为 6,剩余 [6,4,5];再合并全部三堆,费用为 15,总费用为 21。先合并其他连续三堆会得到更高费用。
石堆数量无法按三合一归约到一堆:
输入:stones = [1,2,3,4], k = 3
输出:-1
解释:每次三合一会让石堆总数减少 2;从 4 堆出发只能变为 2 堆,无法继续选择三堆合并,因此不能最终只剩一堆。