合并石头的最低成本
有 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