在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

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

    回到顶部