在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：=一个空堆
对于范围从0到nums大小的i ，执行以下操作
- val:=0
- while h不为空，则执行以下操作
  - [val，index]：= h [0]
  - 如果index≥i-k，则退出循环
  - 否则，删除堆h顶部
- ans：=nums [i] +val
- 将成对（ans，i）插入到堆h中
返回ans

让我们看下面的实现以更好地了解 –

更多Python相关文章，请阅读：Python 教程

示例

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))