LeetCode 70. 爬楼梯题解：斐波那契数列的动态规划建模与 O(1) 空间压缩（附 Python / Java / C++ 实现）-育师

LeetCode 70. 爬楼梯题解：斐波那契数列的动态规划建模与 O(1) 空间压缩（附 Python / Java / C++ 实现）

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book

本篇文章基于《Krahets 笔面试精选 88 题》题解文档 70. 爬楼梯，系统讲解 LeetCode 第 70 题的完整解法：从"最后一步只有跳 1 级或 2 级"的直觉出发，将问题严格建模为斐波那契数列，给出动态规划的四大要素（状态定义、转移方程、初始状态、返回值），并进一步用滚动变量把空间复杂度从 O(N) 压到 O(1)。文末结合当前仓库中三语言解题代码（Python / Java / C++）逐行对照印证，并顺带梳理与本题同源的 509. 斐波那契数、LCR 127. 跳跃训练等变形题。读完你可以彻底掌握"斐波那契类 DP"的通用分析套路，并能够举一反三解决同族题目。

一、问题理解：从"跳法"到递推关系

题目要求计算爬 n 级台阶的不同方法数，约束是每次只能爬 1 级或 2 级。题解文档给出了一个非常干净的建模视角：关注青蛙（或人）的最后一步。

设跳上 n 级台阶有 f(n) 种跳法。在所有跳法中，最后一步只有两种情况：

最后跳 1 级：此时已经站在第 n-1 级台阶上，前 n-1 级台阶的跳法数为 f(n-1)；
最后跳 2 级：此时已经站在第 n-2 级台阶上，前 n-2 级台阶的跳法数为 f(n-2)。

由于两种情况的最后一步互斥，总的跳法数就是两者之和：

f(n) = f(n-1) + f(n-2)

这正是斐波那契数列的递推性质。因此本题可完全转化为"求斐波那契数列的第 n 项"，唯一区别在于初始值不同：

问题	f(0)	f(1)	f(2)
爬楼梯（青蛙跳台阶）	1	1	2
标准斐波那契数列	0	1	1

以爬楼梯为例验证：f(0)=1（不跳视为 1 种空方案，便于递推）、f(1)=1（跳 1 级）、f(2)=2（1+1 或 2），f(3)=f(2)+f(1)=3（111、12、21），与直觉完全吻合。

二、动态规划解析：四要素拆解

题解文档将动态规划解法明确拆为四个要素，这是复用的核心框架：

状态定义：设 dp 为一维数组，其中 dp[i] 的值代表斐波那契数列（即爬楼梯跳法数）的第 i 个数字；
转移方程：dp[i + 1] = dp[i] + dp[i - 1]，即对应数列定义f(n + 1) = f(n) + f(n - 1)；
初始状态：dp[0] = 1, dp[1] = 1，初始化前两个数字；
返回值：dp[n]，即斐波那契数列（爬楼梯跳法数）的第 n 个数字。

需要说明：原文档插图（台阶跳法示意）托管在力扣图床，仓库内并未保存该图片资源，因此本文以文字形式完整还原了该图所要传达的递推逻辑——第 n 级跳法由第 n-1 级与第 n-2 级两种"最后一步"的跳法数相加得到。

三、状态压缩：空间复杂度从 O(N) 降到 O(1)

如果严格按 dp 数组实现，需要新建长度为 n 的列表，空间复杂度为 O(N)。但注意观察转移方程：

dp 列表第 i 项只与第 i-1 和第 i-2 项有关，更早的历史状态在计算完成后不再被引用。

因此只需初始化三个整型变量sum、a、b，利用辅助变量sum暂存a + b，再让a, b两数字交替前进（滚动更新）即可。省去了整个 dp 列表空间，空间复杂度降至 O(1)，这就是"滚动变量"式的状态压缩。这一思路在仓库内的三语言代码中均有直接体现（详见下一节）。

四、三语言代码实现（仓库源码对照）

原文档给出了 Python、Java、C++ 三种实现，且当前仓库 selected_coding_interview/codes 目录下保存了与文档完全一致的工程化源码，可直接对照阅读。

Python 实现

文档中的核心解法：

class Solution: def climbStairs(self, n: int) -> int: a, b = 1, 1 for _ in range(n - 1): a, b = b, a + b return b

仓库中的工程化版本位于 selected_coding_interview/codes/python/lc_70_climbing_stairs.py，代码结构分为Solution Code（解题类）、Test Case（测试用例区）与Driver Code（驱动入口）三部分，并from include import *引入了仓库公共工具模块（见 selected_coding_interview/codes/python/include）。注意 Python 中a, b = b, a + b的元组赋值天然完成"同时更新"，无需sum辅助变量。

Java 实现

class Solution { public int climbStairs(int n) { int a = 1, b = 1, sum; for(int i = 0; i < n - 1; i++){ sum = a + b; a = b; b = sum; } return b; } }

仓库中的完整版本位于 selected_coding_interview/codes/java/lc_70_climbing_stairs/lc_70_climbing_stairs.java，以package lc_70_climbing_stairs;组织包结构，同样包含Solution类与带main方法的驱动类。由于 Java 不支持元组同时赋值，这里显式使用sum临时变量完成a -> b、b -> sum的滚动更新。

C++ 实现

class Solution { public: int climbStairs(int n) { int a = 1, b = 1, sum; for(int i = 0; i < n - 1; i++){ sum = a + b; a = b; b = sum; } return b; } };

仓库中的完整版本位于 selected_coding_interview/codes/cpp/lc_70_climbing_stairs/lc_70_climbing_stairs_s1.cpp，是三种语言中唯一补全了可运行测试驱动的版本：其main函数中构造了测试用例n = 2，调用slt->climbStairs(n)后通过cout << res << endl;输出结果（预期输出 2），可以直接编译运行验证算法正确性。该文件还#include "../include/include.hpp"引用了 C++ 公共头文件目录。

三种语言的循环次数均为n - 1，因为初始b = f(1) = 1已覆盖第 1 项，之后每迭代一次把指针向前推进一级，n-1 轮后b恰好为f(n)。以 n=2 为例：只迭代 1 轮，b = 1 + 1 = 2，正确。

五、复杂度分析

时间复杂度 O(n)：计算 f(n) 需循环 n 次，每轮循环内只做常数次加法与赋值，单轮开销 O(1)，总开销 O(n)；
空间复杂度 O(1)：只使用a、b、sum（或循环变量）等常数个变量，不随 n 增长。

六、同类变形题：从仓库中看斐波那契族题目的演进

理解了"最后一步"的建模方式后，同一思想可以迁移到仓库中另外两道同源题目：

509. 斐波那契数：本题的直接母题。区别仅在初始值f(0)=0, f(1)=1，且循环体写为a, b = b, a + b; return a。仓库源码见 selected_coding_interview/codes/python/lc_509_fibonacci_number.py。对照阅读可以清晰看到"初始值不同 → 返回变量不同"这一唯一差异；
LCR 127. 跳跃训练（对应剑指 Offer 10-II 青蛙跳台阶）：与本题题目背景完全一致，但额外引入了大数越界防护——因为随 n 增大 f(n) 会超过 Int32/Int64 范围，需要在每轮循环中执行sum = (a + b) % 1000000007。其依据是模运算分配律(x + y) ⊙ p = (x ⊙ p + y ⊙ p) ⊙ p，逐轮取模与最终取模等价，可保证中间结果不溢出。

这条"爬楼梯 → 斐波那契 → 取模防溢出"的进阶路径，正是面试中考察动态规划基础能力的经典组合，建议三题连刷对照。

七、小结

本文围绕 70. 爬楼梯题解文档的核心内容，完整梳理了该题从问题建模（最后一步分类）、递推归纳（斐波那契数列）、动态规划四要素，到状态压缩（O(N) → O(1)）的完整推理链条，并给出了 Python / Java / C++ 三种语言的可运行代码及仓库源码位置。掌握这套"斐波那契类 DP"的分析框架后，你可以快速迁移到跳跃训练、斐波那契数等一切具有f(n) = f(n-1) + f(n-2)结构的题目中。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考