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