在python中找到最多k步达到最终索引的最低成本的程序

假设我们有一个数字列表 nums 和另一个值 k。这里 nums[i] 处的项目表示在索引 i 处着陆的成本。如果我们从索引 0 开始并在 nums 的最后一个索引处结束。在每一步中，我们都可以从某个位置 X 跳到最多 k 步远的任何位置。我们必须最小化成本总和才能达到最后一个指数，那么最小总和是多少？

因此，如果输入类似于 nums = [2, 3, 4, 5, 6] k = 2，那么输出将是 12，因为我们可以选择 2 + 4 + 6 以获得最小成本 12。

为了解决这个问题，我们将按照以下步骤操作 -

• 答：= 0

• h := 空堆

• 对于 i 在 0 到 nums 大小的范围内，请执行

• [val, index] := h[0]

• 如果指数 >= i - k，则

• 否则，

• 从循环中出来

• 从堆 h 中删除 top

• 价值：= 0

• 当 h 不为空时，做

• ans := nums[i] + val

• 将 (ans, i) 对插入堆 h

• 返回答案

让我们看看以下实现以获得更好的理解 -

在线示例

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