在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