Python程式：查詢在最多k步內到達最終索引的最小成本

假設我們有一個數字列表 nums 和另一個值 k。這裡 nums[i] 中的專案表示到達索引 i 的成本。如果我們從索引 0 開始，並在 nums 的最後一個索引處結束。在每一步中，我們都可以從某個位置 X 跳到最多 k 步之外的任何位置。我們必須最小化到達最後一個索引的成本總和，那麼最小總和是多少？

因此，如果輸入類似於 nums = [2, 3, 4, 5, 6] k = 2，則輸出將為 12，因為我們可以選擇 2 + 4 + 6 以獲得 12 的最小成本。

為了解決這個問題，我們將遵循以下步驟：

  • ans := 0
  • h := 一個空的堆
  • 從 i = 0 到 nums 的大小，執行以下操作：
    • val := 0
    • 當 h 不為空時，執行以下操作：
      • [val, index] := h[0]
      • 如果 index >= i - k，則
        • 退出迴圈
      • 否則，
        • 從堆 h 中刪除頂部元素
    • ans := nums[i] + val
    • 將 (ans, i) 對插入堆 h 中
  • 返回 ans

讓我們看看以下實現，以便更好地理解：

示例

線上演示

from heapq import heappush, heappop
class Solution:
   def solve(self, nums, k):
      ans = 0
      h = []
      for i in range(len(nums)):
         val = 0
         while h:
            val, index = h[0]
            if index >= i - k:
               break
            else:
               heappop(h)
         ans = nums[i] + val
         heappush(h, (ans, i))
      return ans

ob = Solution()
nums = [2, 3, 4, 5, 6]
k = 2
print(ob.solve(nums, k))

輸入

[2, 3, 4, 5, 6], 2

輸出

12

更新於: 2020年12月2日

189 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告