企业官网建设流程全解析

• 教程

本文是「带你快速刷完 67 道剑指 Offer」系列的第 8 题解析，围绕经典面试题青蛙跳台阶展开。题目本身是斐波那契数列的变种，也是动态规划入门最典型的递推模型之一，面试中出现频率极高。读完本文，你将完整掌握该题的三种解法（朴素递归、循环迭代、斐波那契递推），理解"为什么递归很耗时、循环更快"的底层原因，并能顺势解决其进阶变体——变态跳台阶与矩阵覆盖，为后续 DP 题目打下基础。

题目描述与题意理解

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

本题出自《何海涛. 剑指 Offer[M]. 电子工业出版社, 2012.》一书的第 8 题，也是牛客网《剑指 Offer》专题中的经典入门题，原题收录于 08-剑指offer.md。

关键约束与边界

• 青蛙每次只能跳 1 级或 2 级，不能跳更多；
• 跳法按顺序区分：例如 n=3 时，1+2与2+1算两种不同跳法；
• 边界条件：n=1 时只有 1 种跳法（跳 1 级）；n=2 时有 2 种跳法（1+1 或直接跳 2 级）。

递推关系的建立

设f(n)表示跳上 n 级台阶的跳法总数。考虑最后一步：

• 若最后一步跳 1 级，则此前处于第 n-1 级，方案数为f(n-1)；
• 若最后一步跳 2 级，则此前处于第 n-2 级，方案数为f(n-2)。

两种情况互斥且穷尽，因此得到递推式：

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

这正是斐波那契数列的形式（仅初值不同：经典斐波那契为 1、1，本题为 1、2）。这一步"找到子问题并建立状态转移方程"的思路，就是动态规划解题的第一步，与仓库中动态规划专题强调的"问题的拆解、找到当前问题和子问题的联系"完全一致。

解法一：朴素递归——真的很耗时

原题给出的第一种实现是直接按照递推式书写递归：

int jumpFloor(int number) { if (number == 1) return 1; if (number == 2) return 2; return jumpFloor(number - 1) + jumpFloor(number - 2); }

为什么"真的很耗时"

这段代码逻辑完全正确，但存在严重的性能问题：大量重复子问题。以jumpFloor(5)为例，计算jumpFloor(4)时需要计算jumpFloor(3)、jumpFloor(2)；计算jumpFloor(3)又需要jumpFloor(2)、jumpFloor(1)……子问题被反复计算。

可以推断其时间复杂度为O(2^n)量级（递归树规模呈指数膨胀），空间复杂度 O(n)（递归栈深度）。当 n 稍大（如 n=40）时，计算量将膨胀到数十亿次，在面试机试环境中会严重超时，因此朴素递归只适合帮助理解递推关系，不适合作为提交答案。

解法二：直接循环——从顶向下改为自底向上

原题给出的第二种实现用三个变量滚动更新，把"递归树"变成了"线性递推"，是面试中最推荐的写法之一：

int jumpFloor(int number) { if (number == 1) { return 1; } int first = 1; // f(1) int second = 2; // f(2) for (int i = 3; i <= number; ++i) { int third = first + second; // f(i) = f(i-1) + f(i-2) first = second; second = third; } return second; }

复杂度分析

• 时间复杂度 O(n)：一次线性循环即可求出结果；
• 空间复杂度 O(1)：只使用first、second、third三个常量级变量，不需要开数组。

这里其实就是在用"滚动变量"做自底向上的动态规划：从最小的子问题f(1)、f(2)出发，逐步递推到目标f(n)。对比解法一的 O(2^n) 时间，提升是数量级的，这也印证了原文档"直接循环会好很多"的结论。

解法三（二刷）：本质就是斐波那契数列

阿秀二刷该题时的记录为：运行时间 3ms，占用内存 376k（牛客网评测环境下的实测数据），实现如下：

int jumpFloor(int number) { if (number <= 2) return number; // 0 1 2 直接返回即可 int first = 1, second = 2, third = 0; for (int i = 3; i <= number; ++i) { third = first + second; first = second; second = third; } return third; }

与解法二的区别仅在于收尾：循环结束后直接返回third，同时用if (number <= 2) return number;统一处理了 n=0、1、2 的边界（n=0 时返回 0，虽然题目通常从 n≥1 讨论，但这样写让函数更健壮）。

数列对照

可以看到数列 1、2、3、5、8、13……相邻项之比趋近黄金比例，其递推结构就是斐波那契数列。因此，这道题与剑指 Offer 第 7 题「斐波那契数列」、第 10 题「矩阵覆盖」本质上共用同一套模板，这在剑指 Offer 全集中均有完整实现记录。

仓库佐证：同一模板的三道变体题

为了印证"跳台阶是斐波那契模板"这一结论，可以在仓库中对照阅读同一系列的相邻题目：

No.7 斐波那契数列——最原始的模板

剑指 Offer 第 7 题要求输出斐波那契数列第 n 项（从 0 开始），其最优实现与跳台阶的滚动变量写法如出一辙：

int Fibonacci(int n) { if (n == 0) return 0; if (n == 1) return 1; int first = 0, second = 1, third = 1; for (int i = 2; i <= n; ++i) { third = first + second; first = second; second = third; } return third; }

（完整代码见 剑指offer全集.md 中 No.7 一节。）对比可见：跳台阶只是把初值从f(0)=0, f(1)=1换成了f(1)=1, f(2)=2，其余循环逻辑完全相同。

No.10 矩阵覆盖——同样的递推，换了层外衣

我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，总共有多少种方法？

仔细分析可知：覆盖 2*n 矩形时，若第一块竖放则剩下 2*(n-1)，若横放则必然配套一块横放占据两行，剩下 2*(n-2)，于是f(n) = f(n-1) + f(n-2)，与跳台阶完全一致。其实现见 10-剑指offer.md。

这一系列题目告诉我们一个重要的面试经验：识别"斐波那契类递推"是解题关键——凡是"到达状态 n 的方式只与 n-1、n-2（或更早的有限状态）有关"的问题，都可以套用滚动变量的 O(n) 时间、O(1) 空间解法。

延伸进阶：No.9 变态跳台阶

跳台阶题目末尾的锚点直指下一题——09-剑指offer.md 中的「变态跳台阶」，作为本专题的必做延伸，一并讲解。

题目描述

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

与第 8 题唯一区别：每次可以跳任意级（1 到 n 级）。

递推推导

因为 n 级台阶，第一步有 n 种跳法：跳 1 级、跳 2 级……直到跳 n 级：

• 跳 1 级，剩下 n-1 级，跳法数为 f(n-1)；
• 跳 2 级，剩下 n-2 级，跳法数为 f(n-2)；
• ……
• 跳 n 级，一步到位，跳法数为 f(0)（约定为 1）。

所以f(n) = f(n-1) + f(n-2) + ... + f(1) + f(0)。

又因为f(n-1) = f(n-2) + f(n-3) + ... + f(1) + f(0)，两式相减可得：

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

即这是一个等比数列：f(1)=1，f(2)=2，f(3)=4……通项为f(n) = 2^(n-1)。

三种实现

原文档给出了三种写法，复杂度依次优化：

写法一：递归（借助推导式 f(n)=2*f(n-1)）

int jumpFloorII(int number) { if (number == 1) return 1; return 2 * jumpFloorII(number - 1); }

写法二：循环递推

int jumpFloorII(int number) { if (number == 1) return 1; int count = 0, a = 1; for (int i = 2; i <= number; ++i) { count = a * 2; a = count; } return count; }

写法三（二刷，最优）：直接套用等比数列通项

int jumpFloorII(int number) { if (number <= 1) return number; return pow(2, number - 1); }

阿秀二刷该题的实测记录为：运行时间 4ms，占用内存 488k。第三种写法把递推化简为2^(n-1)的幂运算，时间复杂度 O(log n)（pow内部）甚至 O(1)，是本题的最优解，也再次验证了"先找规律、再编码"的做题思路。

复杂度对比与面试要点总结

面试中被问到本题时，建议按以下路径作答，可以清晰展示思路层次：

1. 先说明递推关系：f(n) = f(n-1) + f(n-2)，边界f(1)=1、f(2)=2；
2. 指出朴素递归存在大量重复子问题，时间复杂度指数级，不可取；
3. 给出滚动变量的迭代写法，说明其 O(n) 时间、O(1) 空间的优势；
4. 点明本质是斐波那契数列变种，并主动延伸"如果一次可以跳任意级"的变体（答案为 2^(n-1)），展示思维的广度。

系列学习指引

• 本题完整题解与代码注释见 08-剑指offer.md，全集汇总见 剑指offer全集.md；
• 想按题号顺序系统刷完 67 道题，可先阅读系列导读，该专栏题目顺序与牛客网《剑指 Offer》专题保持一致；
• 若对递推与 DP 状态设计还不熟练，可先补算法基础中的复杂度概念，再通过动态规划专题的字符匹配类题目练习"拆解子问题、画表找状态"的方法；
• 高频面试题中斐波那契类递推与排序等基础同样重要，可参考高频算法题按频率针对性复习。

• 教程