Python中合并石头的最小成本程序

假设有N堆按顺序排列的石头，其中第i堆有 stones[i] 颗石头。将K个相邻的堆合并成一堆，此操作的成本等于这K堆石头中的总数。我们必须找到将所有石头堆合并成一堆的最小成本。如果无法实现此解，返回-1。

因此，如果输入是 nums = [3,2,4,1]，K = 2，则输出将是20，因为最初有[3、2、4、1]。然后合并成代价为5的[3、2]，我们有[5、4、1]。之后通过代价为5合并[4、1]，我们有[5、5]。然后通过代价为10合并[5、5]，我们有[10]。因此，总成本为20，这是最小成本。

要解决此问题，我们将遵循以下步骤−

n := nums的大小
如果 (n-1) mod (K-1) 不等于 0 ，则
- 返回-1
dp := 一个 n x n的数组，并填充为0
sums := 大小为(n+1)的数组，并将其填充为0
对于i在1到n的范围内，执行以下操作：
- sums[i] := sums[i-1]+nums[i-1]
对于长度在K到n的范围内，执行以下操作：
- 对于 i 在 0 到 n-length 的范围内，执行以下操作：
  - j := i+length-1
  - dp[i, j] := 无限大
  - 对于每一步平均更新K-1，t在范围 i 到 j-1 中，执行以下操作：
  - dp[i][j] = dp[i, t] + dp[t+1, j] 的最小值
  - 如果 (j-i) mod (K-1)与 0 相同，则
  - dp[i, j] := dp[i, j] + sums[j+1]-sums[i]
返回 dp[0, n-1]

示例

看下面的实现以获得更好的理解

import heapq
def solve(nums, K):
    n = len(nums)
    if (n-1)%(K-1) != 0:
        return -1
    dp = [[0]*n for _ in range(n)]
    sums = [0]*(n+1)
    for i in range(1,n+1):
        sums[i] = sums[i-1]+nums[i-1]
    for length in range(K,n+1):
      for i in range(n-length+1):
         j = i+length-1
        dp[i][j] = float('inf')
         for t in range(i,j,K-1):
            dp[i][j] = min(dp[i][j], dp[i][t]+dp[t+1][j])
         if (j-i)%(K-1)==0:
            dp[i][j] += sums[j+1]-sums[i]
   return dp[0][n-1]

nums = [3,2,4,1]
K = 2
print(solve(nums, K))