在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