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)爬楼梯青蛙跳台阶112标准斐波那契数列011以爬楼梯为例验证f(0)1不跳视为 1 种空方案便于递推、f(1)1跳 1 级、f(2)211 或 2f(3)f(2)f(1)3111、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)。以 n2 为例只迭代 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)结构的题目中。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考