Python程序：查找合并石头的最小成本

假设我们有N堆石头排成一排。这里第i堆有stones[i]个石头。一次移动包括将K个连续的堆合并成一堆，这次移动的成本等于这K堆石头的总数。我们必须找到将所有石堆合并成一堆的最小成本。如果没有这样的解决方案，则返回-1。

因此，如果输入类似于nums = [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，这是最小的。

为了解决这个问题，我们将遵循以下步骤：

  • 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]

  • 对于length从K到n，执行

    • 对于i从0到n-length，执行

      • j := i+length-1

      • dp[i, j] := 无穷大

      • 对于t从i到j-1，每次递增K-1，执行

        • dp[i][j] = 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]

示例

让我们看看下面的实现以更好地理解

Open Compiler
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))

输入

[3,2,4,1], 2

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

20

更新于：2021年10月7日

227次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告