1000. 合并石头的最低成本【困难】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 区间 DP

1. 📝 题目描述

• leetcode

有 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

2. 🎯 s.1 - 区间 DP

js

/**
 * @param {number[]} stones
 * @param {number} k
 * @return {number}
 */
var mergeStones = function (stones, k) {
  const n = stones.length
  // 无法合并成一堆的情况：每次合并减少 k-1 堆，最终需要剩 1 堆
  if ((n - 1) % (k - 1) !== 0) return -1

  // 计算前缀和，用于快速获取区间和
  const prefixSum = new Array(n + 1).fill(0)
  for (let i = 0; i < n; i++) {
    prefixSum[i + 1] = prefixSum[i] + stones[i]
  }

  // dp[i][j][p] 表示将 [i, j] 区间合并成 p 堆的最小成本
  const dp = Array.from({ length: n }, () =>
    Array.from({ length: n }, () => new Array(k + 1).fill(Infinity)),
  )

  // 初始化：单个石头堆本身就是 1 堆，成本为 0
  for (let i = 0; i < n; i++) {
    dp[i][i][1] = 0
  }

  // 枚举区间长度
  for (let len = 2; len <= n; len++) {
    // 枚举区间起点
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1
      // 枚举合并成 p 堆的情况
      for (let p = 2; p <= k; p++) {
        // 枚举分割点：将 [i, j] 分成 [i, mid] 和 [mid+1, j]
        // [i, mid] 合并成 1 堆，[mid+1, j] 合并成 p-1 堆
        for (let mid = i; mid < j; mid += k - 1) {
          dp[i][j][p] = Math.min(
            dp[i][j][p],
            dp[i][mid][1] + dp[mid + 1][j][p - 1],
          )
        }
      }
      // 将 k 堆合并成 1 堆的成本 = 先合并成 k 堆 + 这 k 堆的总和
      dp[i][j][1] = dp[i][j][k] + (prefixSum[j + 1] - prefixSum[i])
    }
  }

  return dp[0][n - 1][1]
}

• 时间复杂度：$O(n^3\times k)$，其中 n 是石头堆数，需要枚举区间、堆数和分割点
• 空间复杂度：$O(n^2\times k)$，三维 DP 数组的空间

算法思路：

• 合并可行性判断：每次合并减少 k-1 堆，从 n 堆到 1 堆需要 (n-1) % (k-1) === 0
• 定义状态：dp[i][j][p] 表示将区间 [i, j] 合并成 p 堆的最小成本
• 初始化：dp[i][i][1] = 0，单堆本身就是 1 堆，成本为 0
• 状态转移：枚举分割点 mid，将 [i, j] 分为 [i, mid] 合并成 1 堆和 [mid+1, j] 合并成 p-1 堆，注意 mid 步长为 k-1
• 最终合并：dp[i][j][1] = dp[i][j][k] + sum[i, j]，先合并成 k 堆再合并成 1 堆