题目：

  1. 有 N 堆石头排成一排，第 i 堆中有 stones[i] 块石头。
  3. 每次移动（move）需要将连续的 K 堆石头合并为一堆，而这个移动的成本为这 K 堆石头的总数。
  5. 找出把所有石头合并成一堆的最低成本。如果不可能，返回 -1 。
  7. 示例 1：
  9. 输入：stones = [3,2,4,1], K = 2
  10. 输出：20
  11. 解释：
  12. 从 [3, 2, 4, 1] 开始。
  13. 合并 [3, 2]，成本为 5，剩下 [5, 4, 1]。
  14. 合并 [4, 1]，成本为 5，剩下 [5, 5]。
  15. 合并 [5, 5]，成本为 10，剩下 [10]。
  16. 总成本 20，这是可能的最小值。
  18. 来源：力扣（LeetCode）
  19. 链接：https://leetcode-cn.com/problems/minimum-cost-to-merge-stones
  20. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

答案：

时间：

没做出来

  1. class Solution:
  2.     def mergeStones(self, stones: List[int], K: int) -> int:
  3.         n=len(stones)
  5.         if (n-1)%(K-1):return -1
  7.         prefix = [0] * (n+1)
  8.         for i in range(1,n+1): prefix[i] = stones[i-1] + prefix[i-1]
  10.         @functools.lru_cache(None)
  11.         def dp(i, j, m):
  12.             if i == j:
  13.                 return 0 if m == 1 else float("inf")
  14.             if m == 1:
  15.                 return dp(i, j, K) + prefix[j + 1] - prefix[i]
  16.             temp=float("inf")
  17.             for mid in range(i, j, K - 1):
  18.                 temp=min(temp, dp(i, mid, 1) + dp(mid + 1, j, m - 1) )
  19.             return temp
  20.         res = dp(0, n - 1, 1)
  21.         return res

要点：

1. 这题目 太复杂了，考虑的要素过多。。。

其他：

代码报错：无