CS-Notes 剑指 Offer 动态规划:跳台阶问题的递推建模与 O(1) 空间解法

本文基于 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 级台阶,青蛙倒数第一步只有两种可能——

1. 从第 n-1 级跳 1 级上来,那么前 n-1 级的跳法总数就是 f(n-1);
2. 从第 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 跳台阶 的完整解题脉络,面试作答可按以下逻辑链组织:

1. 建模:按"最后一跳"划分状态,得到 f(n) = f(n-1) + f(n-2),初始条件 f(1) = 1、f(2) = 2;
2. 排除:朴素递归存在大量重叠子问题,时间复杂度指数级,不可取;
3. 实现:自底向上迭代,且利用"状态只依赖前两项"这一性质,用 pre2/pre1 滚动变量把空间压到 O(1);
4. 延伸:主动提及矩形覆盖(同方程)、斐波那契(同型递推)、变态跳台阶(等比数列化简 2^(n-1))三道关联题,展示对整个 DP 专题的把握。

这套"划分最后一步 → 写出转移方程 → 迭代滚动优化"的三步法,可直接迁移到绝大多数一维递推类面试题,是 CS-Notes 动态规划专题最具复用价值的方法论。