在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, heappopclass 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
以上是 在python中找到最多k步达到最终索引的最低成本的程序 的全部内容, 来源链接: utcz.com/z/350522.html