 空间解法)
CS-Notes 剑指 Offer 动态规划:跳台阶问题的递推建模与 O(1) 空间解法
【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes
本文基于 CS-Notes 仓库中「剑指 Offer」动态规划专题的跳台阶题解,围绕"青蛙每次跳 1 级或 2 级台阶,求跳上 n 级台阶的跳法总数"这一问题展开:从递推公式的推导、朴素递归的缺陷,到滚动变量实现的空间优化,完整给出可复现的 Java 解法,并串联斐波那契数列、矩形覆盖、变态跳台阶三道同型题目,帮助读者掌握"递推建模范式"与"O(1) 空间动态规划"两类面试核心能力。
一、问题定义
一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
这道题出自「剑指 Offer」经典题库,在 CS-Notes 的剑指 Offer 题解目录中被归入「动态规划」专题,与 10.1 斐波那契数列、10.2 矩形覆盖、10.4 变态跳台阶 组成一组同型题。
二、递推建模:从小规模实例中找规律
先观察两个最小规模的边界情况,它们是后续递推公式的基石:
- n = 1 时,只有 1 种跳法:即"跳 1 级"。
- n = 2 时,有 2 种跳法:先跳 1 级再跳 1 级,或者一次跳 2 级。
关键在于最后一跳的状态划分:要跳上第 n 级台阶,青蛙倒数第一步只有两种可能——
- 从第 n-1 级跳 1 级上来,那么前 n-1 级的跳法总数就是
f(n-1); - 从第 n-2 级跳 2 级上来,那么前 n-2 级的跳法总数就是
f(n-2)。
两种情况互斥且穷尽,因此得到递推公式(原文档以图片形式给出):
用数学语言表述即:
f(1) = 1 f(2) = 2 f(n) = f(n-1) + f(n-2), n > 2从源码结构看,这个递推关系与 CS-Notes 中 10.1 斐波那契数列 的f(n) = f(n-1) + f(n-2)完全同型,只是初始条件不同——跳台阶本质上是偏移了一位、且从 1, 2 起步的斐波那契数列;10.2 矩形覆盖(用 n 个 2×1 小矩形覆盖 2×n 大矩形)的递推公式也与之一字不差。三者共享同一套求解框架:确定初始条件 → 写出状态转移方程 → 自底向上迭代。
三、解法演进:从朴素递归到滚动变量
3.1 朴素递归:指数级开销
按递推式直接写递归,是最直觉的写法:
public int JumpFloor(int n) { if (n <= 2) return n; return JumpFloor(n - 1) + JumpFloor(n - 2); }但正如 10.1 斐波那契数列 中所分析的那样,递归会把子问题反复计算:计算f(5)需要计算f(4)和f(3),而f(4)内部又要计算f(3)和f(2),f(3)被重复求解。调用树近似呈二叉展开,时间复杂度为指数级 O(2^n),n 稍大(如超过 40)就会超时,面试中不可接受。
3.2 自底向上动态规划:O(n) 时间
用"缓存子问题解"的思路,自底向上填表:
public int JumpFloor(int n) { if (n <= 2) return n; int[] dp = new int[n + 1]; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2]; return dp[n]; }时间复杂度降为 O(n)。但进一步观察可以发现:dp[i]只依赖dp[i-1]与dp[i-2]两个状态,历史状态一旦用完就不再需要。这正是原仓库 10.3 跳台阶 给出的优化方向。
3.3 滚动变量:O(1) 空间(原文档标准解法)
原文档给出的最终实现如下,仅用两个变量pre2、pre1滚动保存前两项:
public int JumpFloor(int n) { if (n <= 2) return n; int pre2 = 1, pre1 = 2; int result = 0; for (int i = 2; i < n; i++) { result = pre2 + pre1; pre2 = pre1; pre1 = result; } return result; }逐行拆解这段代码的参数含义与执行过程:
| 变量 | 初始值 | 含义 |
|---|---|---|
pre2 | 1 | 对应f(1) = 1 |
pre1 | 2 | 对应f(2) = 2 |
result | 0 | 存放当前正在计算的f(i+1) |
循环i = 2; i < n; i++ | — | 从第 3 项开始,共滚动 n-2 次,结束时result恰为f(n) |
以 n = 5 为例跟踪循环:
| 轮次 i | result(即 f(i+1)) | pre2 | pre1 |
|---|---|---|---|
| 2 | 3 = f(3) | 2 | 3 |
| 3 | 5 = f(4) | 3 | 5 |
| 4 | 8 = f(5) | 5 | 8 |
最终返回result = 8,即跳 5 级台阶共 8 种跳法,时间复杂度 O(n)、空间复杂度 O(1)。这与 10.1 斐波那契数列 中"考虑到第 i 项只与第 i-1 和第 i-2 项有关,只需存储前两项,将空间复杂度由 O(N) 降为 O(1)"的优化思想如出一辙。
3.4 边界与数值限制说明
结合原实现if (n <= 2) return n;的写法,从源码结构看,该方法对 n ≤ 0 的输入会直接返回 n 本身(即 0 或负数),题目隐含 n 为正整数这一前提,实际调用前应对输入合法性做校验。另外,由于返回值是int,而跳台阶的解就是斐波那契数列,Fib(47) 已超过 32 位整数上限,因此 n 较大(约 46 以上)时该解法会发生整数溢出;若题目允许 n 更大,可改用long或取模运算,这一点与 10.1 斐波那契数列 中"n ≤ 39"的取值约束是同一类考虑。
四、同型题对照:一道题串起整个 DP 专题
在 CS-Notes 的动态规划分组中,跳台阶是承上启下的一题,建议配合以下文档横向对比学习:
| 题目 | 状态转移方程 | 结果特征 | 文档 |
|---|---|---|---|
| 10.1 斐波那契数列 | f(n) = f(n-1) + f(n-2) | 斐波那契数列本体,可用 O(1) 预计算 | notes/10.1 斐波那契数列.md |
| 10.2 矩形覆盖 | f(n) = f(n-1) + f(n-2) | 与跳台阶同方程同解法 | notes/10.2 矩形覆盖.md |
| 10.3 跳台阶 | f(n) = f(n-1) + f(n-2) | 本文主题,O(n) 时间 + O(1) 空间 | notes/10.3 跳台阶.md |
| 10.4 变态跳台阶 | f(n) = f(n-1) + ... + f(0) | 化为等比数列f(n) = 2^(n-1) | notes/10.4 变态跳台阶.md |
其中 10.4 变态跳台阶 是最有价值的变式:若青蛙可以跳 1 级到 n 级,则状态转移变成求和式f(n) = f(n-1) + f(n-2) + ... + f(0)。由相邻两式相减可得f(n) = 2 * f(n-1),即 f(n) 是等比数列,最终解为:
public int JumpFloorII(int target) { return (int) Math.pow(2, target - 1); }对比之下可以清晰看出:「跳台阶」的 O(n) 迭代与「变态跳台阶」的 O(1) 公式解,差异完全来自状态转移方程的形态。面试中被追问"如果青蛙可以跳任意级怎么解",正是靠这种对比能力得分。
五、小结与面试表达要点
回顾 10.3 跳台阶 的完整解题脉络,面试作答可按以下逻辑链组织:
- 建模:按"最后一跳"划分状态,得到
f(n) = f(n-1) + f(n-2),初始条件f(1) = 1、f(2) = 2; - 排除:朴素递归存在大量重叠子问题,时间复杂度指数级,不可取;
- 实现:自底向上迭代,且利用"状态只依赖前两项"这一性质,用
pre2/pre1滚动变量把空间压到 O(1); - 延伸:主动提及矩形覆盖(同方程)、斐波那契(同型递推)、变态跳台阶(等比数列化简
2^(n-1))三道关联题,展示对整个 DP 专题的把握。
这套"划分最后一步 → 写出转移方程 → 迭代滚动优化"的三步法,可直接迁移到绝大多数一维递推类面试题,是 CS-Notes 动态规划专题最具复用价值的方法论。
【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
