在Python中找到攀登楼梯到达顶部的最小代价的程序？

假设我们有一个称为stairs的数字列表和另一个价值k。我们目前在楼梯0和要爬到楼梯的最后一个指数。值stair[i]表示到达索引的成本，在每轮中，我们可以一次跳1,2,…k, levels。我们必须找到爬到最后一个楼梯的最小成本。

因此，如果输入是stairs = [4, 11, 11, 3, 2]，k = 3，则输出将是9，因为我们使用楼梯 [4, 3, 2]

为了解决这个问题，我们将按照以下步骤进行：

q：双端队列，将一对（stairs [0]，0）插入其中
对于i在范围1到stairs的大小，做
- 在i – q [0,1] > k时，执行以下操作
  - 从q的左侧删除项目
- curcost：= q [0,0] + stairs [i]
- 而且q不为空，curcost <= q的最后一项的第一个值，执行以下操作
  - 从q中删除最后一个元素
- 将（curcost，i）插入q的末尾
返回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))