746_使用最小花费爬楼梯

类型：数组

• 746. 使用最小花费爬楼梯 💚

  https://leetcode-cn.com/problems/min-cost-climbing-stairs/

  ❓ 数组 cost 表示到达每个台阶需要花费的体力值。每次可以向上爬一个台阶或两个台阶。求到达顶部的最低体力花费。你可以选择第 0 或第 1 级作为起始台阶。

  💡 动态规划

  第 i 级台阶可以由第 i - 1 级到达，也可以由第 i - 2 级到达。

  转移方程：dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

  由于 dp[i] 只与 dp[i - 1] 和 dp[i - 2] 有关，因此可以只保存前两个记录，优化空间。

  class Solution:
      def minCostClimbingStairs(self, cost: List[int]) -> int:
          pays = [0, 0]
          for i in range(2, len(cost) + 1):
              pay = min(pays[0] + cost[i - 2], pays[1] + cost[i - 1])
              pays[0], pays[1] = pays[1], pay
          return pays[1]

  时间复杂度：O(n)，空间复杂度：O(1)