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 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告