Pythonで階段の一番上に登るのに最小限のコストを取得するためのプログラムはありますか？

階段と呼ばれる数のリストと別の値kがあるとします。現在、階段0にあり、最後の階段のインデックスに登りたいと考えています。値stair[i]は、インデックスに到達するためのコストを示し、各ラウンドで1、2、...kの階段を一度にジャンプできます。最後の階段に登るのに必要な最小費用を見つける必要があります。

したがって、入力がstairs =[4、11、11、3、2] k =3の場合、stairs [4、3、2]

これを解決するために、次の手順に従います

• q：=両端キューで、ペア（stairs [0]、0）を挿入します

• 1から階段のサイズまでの範囲のiの場合、実行します

  • i --q [0、1]> k、do

    • qの左側からアイテムを削除します

  • curcost：=q [0、0]+階段[i]

  • qが空ではなく、curcost <=qの最後の項目の最初の値である場合、実行します

    • qから最後の要素を削除する

  • qの最後に（curcost、i）を挿入します

• qの最後の項目の最初の値を返す

理解を深めるために、次の実装を見てみましょう

例

from collections import deque

class Solution:
   def solve(self, stairs, k):
      q = deque([(stairs[0], 0)])
      for i in range(1, len(stairs)):
         while i - q[0][1] > k:
            q.popleft()
         curcost = q[0][0] + stairs[i]
         while q and curcost <= q[-1][0]:
            q.pop()
         q.append((curcost, i))
      return q[-1][0]

ob = Solution()
stairs = [4, 11, 11, 3, 2]
k = 3
print(ob.solve(stairs, k))

入力

[4, 11, 11, 3, 2], 3

出力

9