用 Python 编写程序，找出爬上楼梯顶部所需的最小成本?

pythonserver side programmingprogramming更新于 2026/2/16 14:04:17

假设我们有一个数字列表，称为楼梯和另一个值 k。我们目前位于楼梯 0，想要爬到楼梯的最后一个索引。值 stair[i] 表示到达索引所需的成本，在每一轮中，我们可以一次跳过 1、2、... k 个楼梯。我们必须找到爬到最后一步楼梯的最低成本。

因此，如果输入为 ladder = [4, 11, 11, 3, 2] k = 3，则输出为 9，因为我们使用的 ladder 为 [4, 3, 2]

为了解决这个问题，我们将遵循以下步骤

q := a double endsqueue and insert a pair (stairs[0], 0) into it
for i in range 1 to size of ladder, do
- while i - q[0, 1] > k，do
  - 从 q 左侧删除项目
- curcost := q[0, 0] + ladder[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))