BM64　最小花费爬楼梯¶

简单通过率 44.51%python3核心代码模式样例通过牛客 AC动态规划

牛客原题　源码

讲解章节：DP 入门

一句话

到达每一阶的最小花费，滚动两个变量推到顶部。

解题思路¶

这题考什么¶

状态该定义成「到达」还是「站在」，取决于费用记在哪个动作上。题面说的是「支付 cost[i] 才能从第 i 阶往上爬」——费用记在离开台阶时，到达一阶本身不花钱。把这句读反，边界就会整体错一层。

状态定义：dp[i] = 到达第 i 阶所需的最小花费；楼梯顶部记作第 n 阶（n = len(cost)）。转移方程：

dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])       i >= 2
dp[0] = dp[1] = 0            两个起步位置都免费，谁都可以当出发点

含义是「站在第 i-1 阶付 cost[i-1] 迈一步上来，或站在第 i-2 阶付 cost[i-2] 迈两步上来」。答案是 dp[n]：顶部在最后一级台阶的上方，不是 dp[n-1]。转移只回看两格，用 a = dp[i-2]、b = dp[i-1] 滚动即可，见 DP 入门的滚动数组一节。

数据规模与复杂度¶

n <= 1e5，cost_i <= 1e4，时限 2 秒（其他语言）。单趟线性扫描 1e5 次迭代，时间 O(n)、空间 O(1)，余量极大。花费上界 1e5 * 1e4 = 1e9，Python 整数不溢出，无须额外处理。

坑在哪¶

答案是 dp[n] 而不是 dp[n-1]。返回 dp[n-1] 等于停在最后一级台阶上没登顶，样例 [2,5,20] 会答成 2 而不是 5。
dp[0] 与 dp[1] 都取 0，因为题面允许从下标 0 或 1 起步。只把 dp[0] 置 0、让 dp[1] = cost[0] 会强制从第 0 阶出发，多付一次钱。
n < 2 时顶部就在起步位置，直接返回 0；漏掉这个分支时 range(2, n+1) 虽然为空，但返回的 b 已被初始化成 0，语义靠巧合而非推导成立，写清楚更稳。
cost_i >= 1 全为正，dp 单调不减，不存在「多走一步反而更省」的反直觉情形。

样例复核¶

cost = [2, 5, 20]，dp[0] = dp[1] = 0； dp[2] = min(dp[1] + 5, dp[0] + 2) = 2； dp[3] = min(dp[2] + 20, dp[1] + 5) = 5，与期望输出 5 一致。

参考实现¶

solutions/nowcoder/BM64/sol.py
from typing import List, Optional


class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        if n < 2:
            return 0                 # 顶部就在第 0/1 阶，两个起步位置任选其一，不用付钱
        # 滚动变量省掉 dp 数组：转移只回看两格。初值 0 对应 dp[0] = dp[1] = 0
        a = b = 0                    # a = dp[i-2], b = dp[i-1]
        for i in range(2, n + 1):    # 上界取 n+1，因为答案是「顶部」这一阶 dp[n]
            x = b + cost[i - 1]      # 从第 i-1 阶付费迈一步上来
            y = a + cost[i - 2]      # 从第 i-2 阶付费迈两步上来
            # 手写比较代替 min()，省掉 1e5 次函数调用；两个候选同时挪位，避免用到新值
            a, b = b, x if x < y else y
        return b                     # 循环结束时 b = dp[n]，即到达顶部的最小花费

BM64 最小花费爬楼梯¶