CS-Notes 剑指 Offer 10.4 变态跳台阶：从 O(n²) 动态规划到 O(1) 直接求 2^(n-1)

本文基于 CS-Notes 仓库中的「剑指 Offer 10.4 变态跳台阶」题解展开，讲解青蛙一次最多可跳 n 级台阶这一经典动态规划问题的两种解法：先用二维 DP 自底向上推导，再通过数学化简把递推式压缩为等比数列。读完后，你能掌握该题完整的状态转移推导过程、两套可直接复制的 Java 实现、各自的时间/空间复杂度，以及 int 溢出的适用边界，并能与系列前作「跳台阶」「矩形覆盖」对照，看清动态规划题型的演化脉络。

题目描述

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级……它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

本题是剑指 Offer 第 10 题系列的最后一问，难度递进关系为：

题目	一次最多可跳	结果形式
10.2 矩形覆盖	2 格	斐波那契数列 f(n) = f(n-1) + f(n-2)
10.3 跳台阶	2 级	斐波那契数列 f(n) = f(n-1) + f(n-2)
10.4 变态跳台阶	n 级	等比数列 f(n) = 2 · f(n-1)

前三题共用“把大问题拆成子问题”的动态规划思路；当单跳步数上限从 2 放开到 n 后，状态转移式从“只依赖前两项”变成了“依赖前面所有项”，解法也随之从滚动数组退化为可以直接闭式求解的等比数列。四道题的完整索引见 剑指 Offer 题解 - 目录 中的“动态规划”小节。

解法一：动态规划（O(n²)）

按题解给出的 DP 思路：设 dp[i] 为跳上第 i+1 级台阶的跳法总数。由于青蛙可以从任意低台阶一次跳到当前台阶，dp[i] 等于前面所有 dp[j] 之和，再加上“直接从地面一步跳到顶”这一种跳法。参考实现如下（来自 10.4 变态跳台阶）：

public int jumpFloorII(int target) {
    int[] dp = new int[target];
    Arrays.fill(dp, 1);
    for (int i = 1; i < target; i++)
        for (int j = 0; j < i; j++)
            dp[i] += dp[j];
    return dp[target - 1];
}

逐行拆解这段代码的细节：

1. Arrays.fill(dp, 1)：初始化把每个 dp[i] 都置 1。其中 dp[0] = 1 对应“1 级台阶只有 1 种跳法”；后续每轮的 +1 部分，则代表“从地面直接跳上当前台阶”这一种跳法，它与逐级累加的 dp[0] + ... + dp[i-1] 共同构成完整转移式：

   f(i) = 1 + f(0) + f(1) + ... + f(i-1)
   

2. 双重循环：外层枚举目标台阶 i，内层把 i 之前所有台阶的跳法累加进来。由于每计算一个 dp[i] 都要扫描一次 [0, i)，总操作量是 1 + 2 + … + (n-1) = O(n²) 次加法。

3. 返回 dp[target - 1]，即 n 级台阶的总跳法。

复杂度：时间 O(n²)，空间 O(n)。以 n = 6 为例验证：f(1)=1，f(2)=2，f(3)=4，f(4)=8，f(5)=16，f(6)=32，与后文 2^(n-1) 的结论完全一致。

解法二：数学推导（O(1)）

题解的核心化简在于把“求和型”递推转化为“乘 2 型”递推。

跳上 n-1 级台阶，可以从 n-2 级跳 1 级上去，也可以从 n-3 级跳 2 级上去……，那么：

f(n-1) = f(n-2) + f(n-3) + ... + f(0)

同样，跳上 n 级台阶，可以从 n-1 级跳 1 级上去，也可以从 n-2 级跳 2 级上去……，那么：

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

两式相减，f(n-2) 到 f(0) 全部抵消，只剩首项：

f(n) - f(n-1) = f(n-1)

即：

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

所以 f(n) 是一个首项 f(1) = 1、公比为 2 的等比数列，通项直接写成：

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

题解给出的 O(1) 实现：

public int JumpFloorII(int target) {
    return (int) Math.pow(2, target - 1);
}

两种解法对比与工程注意

维度	DP 解法	数学解法
时间复杂度	O(n²)	O(1)
空间复杂度	O(n)	O(1)
正确性依据	直接枚举状态转移	依赖等比数列推导
大 n 表现	加法累加，int 溢出较慢	指数增长，target 超过 32 时 int 结果溢出

结合 10.1 斐波那契数列 中展示的空间优化思想（滚动变量只保留必要项）可以推断：如果不用闭式解，DP 解法的内层求和也可以用一个“前缀和”滚动变量维护，把 O(n²) 压到 O(n)；但本题既然存在等比数列的闭式解，O(1) 解法是最终形态，这也是该题在面试中主要考察“能否从求和递推推出乘数递推”这一数学洞察力，而非单纯写 DP。

工程上需要注意：2^(n-1) 增长速度极快，int 类型在 target - 1 >= 31 时即超出 2³¹-1 的上限，(int) Math.pow(...) 会溢出得到错误值。因此在实际使用中：

• 若题目保证 n 较小（如面试环境常见 n < 30），可直接使用上面的 O(1) 写法；
• 若 n 很大且要求精确值，应改用 BigInteger 计算 2 的幂，或按题目要求对某个模数取余（配合快速幂）。

系列延伸

跳台阶系列是动态规划入门的最佳路径，建议按以下顺序对照阅读，体会状态转移式随约束放宽如何演化：

• 10.1 斐波那契数列：递归 → 数组 DP → O(1) 滚动变量的三次优化；
• 10.2 矩形覆盖：用 2×1 矩形铺 2×n 大矩形，转移式 f(n) = f(n-1) + f(n-2)；
• 10.3 跳台阶：一次最多跳 2 级，与矩形覆盖同构；
• 10.4 变态跳台阶：一次最多跳 n 级，化简为等比数列 f(n) = 2^(n-1)。

需要更多动态规划练手题目时，可继续参考仓库中的 Leetcode 题解 - 动态规划，本篇的“状态转移 + 复杂度分析 + 边界注意”的写法可以直接套用到该系列的各题上。