合并石头的最低成本问题

题目描述
有 N 堆石头排成一排，第 i 堆石头的数量为 stones[i]。每次操作需要将连续的 K 堆石头合并为一堆，这次操作的代价是这 K 堆石头的总数。请找出把所有石头合并成一堆的最低成本。如果无法合并成一堆，则返回 -1。

示例
输入：stones = [3, 2, 4, 1], K = 2
输出：20
解释：
步骤1：合并 stones[0] 和 stones[1] (3 + 2 = 5)，成本 = 5，剩余石头 = [5, 4, 1]
步骤2：合并 stones[1] 和 stones[2] (4 + 1 = 5)，成本 = 5，剩余石头 = [5, 5]
步骤3：合并 stones[0] 和 stones[1] (5 + 5 = 10)，成本 = 10，总成本 = 5 + 5 + 10 = 20

解题思路

1. 可行性判断
   每次合并将 K 堆变为 1 堆，相当于每次减少 (K-1) 堆。初始有 N 堆，最终剩 1 堆，需要减少 (N-1) 堆。因此，只有当 (N-1) 能被 (K-1) 整除时，才能合并成一堆。即判断 (N - 1) % (K - 1) == 0。

2. 区间动态规划定义
   定义 dp[i][j] 表示将区间 [i, j] 内的石头合并成若干堆的最小成本。注意：这里不要求合并成一堆，而是合并到无法再合并为止（即堆数小于 K 时停止）。最终目标是 dp[0][N-1]。

3. 状态转移方程

   • 前缀和数组 prefixSum 用于快速计算区间和。
   • 枚举区间长度 len 从 1 到 N。
   • 对于每个区间 [i, j]，枚举分割点 m（从 i 到 j，步长为 K-1），将区间分成 [i, m] 和 [m+1, j]。
     • 左区间 [i, m] 合并后的堆数应为 1（即长度满足 (m-i) % (K-1) == 0），右区间 [m+1, j] 的堆数任意。
     • 转移方程：

       dp[i][j] = min(dp[i][j], dp[i][m] + dp[m+1][j])
       

   • 如果区间 [i, j] 的长度满足 (j-i) % (K-1) == 0，说明可以进一步合并成一堆，此时加上整个区间的石头总成本：

     dp[i][j] += prefixSum[j+1] - prefixSum[i]
     

4. 初始化与计算

   • 初始化 dp[i][i] = 0（单堆无需合并）。
   • 按区间长度从小到大递推。

完整代码示例（Python）

def mergeStones(stones, K):
    n = len(stones)
    if (n - 1) % (K - 1) != 0:
        return -1

    prefixSum = [0] * (n + 1)
    for i in range(n):
        prefixSum[i + 1] = prefixSum[i] + stones[i]

    dp = [[0] * n for _ in range(n)]

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for m in range(i, j, K - 1):
                dp[i][j] = min(dp[i][j], dp[i][m] + dp[m + 1][j])
            if (j - i) % (K - 1) == 0:
                dp[i][j] += prefixSum[j + 1] - prefixSum[i]

    return dp[0][n - 1]

关键点说明

• 分割点 m 的步长为 K-1，确保左区间可合并成一堆。
• 只有当区间长度满足 (len-1) % (K-1) == 0 时才加上区间和，因为只有此时才能进一步合并。
• 时间复杂度 O(N³/K)，通过步长优化减少枚举次数。