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
  • hが空でない間は、
    • [val、index]：=h [0]
    • インデックス>=i --kの場合、
      • ループから抜け出す
    • それ以外の場合、
      • ヒープからトップを削除します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