在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
热门推荐
1 训练狗狗憋尿
2 狗狗追踪训练
3 狗狗训练要多少钱
5 深圳狗狗训练
6 训练狗狗唤回
7 狗狗叫怎么训练
8 狗狗训练班
10 狗狗社会化训练
11 狗狗叫回训练
12 广州狗狗训练学校
13 狗狗训练躺下
14 狗狗随行训练
15 训练狗狗巡回
16 狗狗要怎么训练
17 狗狗喂食训练
18 训练狗狗躺下