使用最小花费爬楼梯

🟢 Easy · 🏷️ 动态规划 · LeetCode#746

📖 题目

cost[i] 是从第 i 个台阶往上爬一次要付的钱，可以选择从第 0 或第 1 阶开始，每次爬 1 或 2 阶，求到达顶部的最小花费。

输入	输出	说明
cost=[10,15,20]	15	从第1阶起步，付15，跳2步到顶

💡 思路

跟爬楼梯是同一个骨架，只是问题从"有多少种方法"换成了"最少花多少钱"——转移方程里的加法要换成取最小值。

到达位置 i 只有两种来路：从 i-1 跳 1 步（花费 dp[i-1] + cost[i-1]），或从 i-2 跳 2 步（花费 dp[i-2] + cost[i-2]），取较小的：

dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

dp[0]、dp[1] 都是 0——题目允许从第 0 或第 1 阶免费起步。

💻 代码

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

时间复杂度 O(n)，空间复杂度 O(1)——跟爬楼梯的优化版一个思路，滚动变量代替数组。