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]

示例

讓我們看看下面的實現以更好地理解

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

輸出

20

更新於：2021年10月7日

227次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告