LC70　爬楼梯¶

简单通过率 55.8%python3核心代码模式动态规划样例通过牛客 AC记忆化数学动态规划

讲解章节：DP 入门

一句话

到第 n 阶的走法只能由第 n-1 阶和第 n-2 阶汇来，于是递推就是斐波那契。

解题思路¶

这题考什么¶

最后一步只有两种可能：从第 n-1 阶迈 1 阶上来，或者从第 n-2 阶迈 2 阶上来。这两类走法没有任何重叠（最后一步的步长不同），也没有遗漏（题目只允许 1 或 2），所以把两边的方案数直接相加就是答案。这就是计数类动态规划的加法原理，见 DP 入门。

状态定义：f[i] 表示恰好走到第 i 阶楼梯的不同走法数。转移方程：

f[i] = f[i-1] + f[i-2]

初值 f[0] = 1、f[1] = 1。f[1] = 1 是显然的（只能迈一个 1 阶）； f[0] = 1 需要一句解释：它表示「还没开始爬」这一种空走法。取 1 而不是 0，是为了让 f[2] = f[1] + f[0] = 2 成立—— 第 2 阶确实有「1+1」和「2」两种走法。若把 f[0] 设成 0，f[2] 会算成 1，整条链全错。

这个递推与斐波那契数列同形，只差一个下标平移，所以答案增长得非常快。

f[i] 只用到紧挨着的两项，于是数组这一维可以整个省掉，只留两个标量滚动：进入第 i 轮时 a = f[i-2]、b = f[i-1]，一次同时赋值就把窗口向右推一格。

数据规模与复杂度¶

1 <= n <= 45。时间 O(n)，最多 44 次加法；空间 O(1)，只有两个整数。与之对照的朴素递归 climb(n) = climb(n-1) + climb(n-2) 不记忆化时，调用次数本身就是斐波那契数量级，n = 45 约 1.8e9 次调用，必然超时；递推等价于自底向上把每个 f[i] 只算一次。

n <= 45 使答案最大为 f[45]，约 1.8e9，超出 32 位有符号整数的一半但仍在范围内； Python 整数任意精度，不必担心溢出，这一点在 C++ 里则要用 long long。

坑在哪¶

f[0] = 1 不是笔误。把它当成「0 阶有 0 种走法」写成 0，会让 f[2] 少算一种，之后每一项都错。这里的 1 代表「什么都不做」这一种方案，是计数 DP 的惯例。
循环次数是 n-1 不是 n。b 起手就已经是 f[1]，再推 n-1 次才到 f[n]；写成 range(n) 会多推一格，返回 f[n+1]。
n = 1 时循环体一次都不进，直接返回初值 b = 1，正是正确答案。换成先算再判断的写法反而要额外挡一层。
a, b = b, a + b 必须是同时赋值。拆成两条语句先写 a = b，再算 b = a + b 时 a 已经被覆盖，等号右边取到的是新值，递推变成 b = 2*b。

样例复核¶

n = 3。初值 a = 1（f[0]）、b = 1（f[1]）。

第 1 轮：a, b = 1, 2      -> f[1] = 1, f[2] = 2
第 2 轮：a, b = 2, 3      -> f[2] = 2, f[3] = 3

返回 3，与样例「1+1+1、1+2、2+1」三种走法一致。

参考实现¶

solutions/leetcode/LC70/sol.py
from typing import List, Optional


class Solution:
    def climbStairs(self, n: int) -> int:
        # 滚动掉的是「阶数」这一维：整个 f 数组压成两个标量。
        # 进入循环前 a = f[0] = 1（空走法，取 1 才能让 f[2] 算出 2）、b = f[1] = 1
        a, b = 1, 1
        # b 起手已是 f[1]，再推 n-1 步才到 f[n]；n = 1 时不进循环，直接返回初值
        for _ in range(n - 1):
            # 同时赋值：右边先整体求值，b 的新值用的仍是旧 a，窗口向右滑一格
            a, b = b, a + b
        return b

LC70 爬楼梯¶