教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载本文是「带你快速刷完 67 道剑指 Offer」系列的第 8 题解析围绕经典面试题青蛙跳台阶展开。题目本身是斐波那契数列的变种也是动态规划入门最典型的递推模型之一面试中出现频率极高。读完本文你将完整掌握该题的三种解法朴素递归、循环迭代、斐波那契递推理解为什么递归很耗时、循环更快的底层原因并能顺势解决其进阶变体——变态跳台阶与矩阵覆盖为后续 DP 题目打下基础。题目描述与题意理解一只青蛙一次可以跳上 1 级台阶也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法先后次序不同算不同的结果。本题出自《何海涛. 剑指 Offer[M]. 电子工业出版社, 2012.》一书的第 8 题也是牛客网《剑指 Offer》专题中的经典入门题原题收录于 08-剑指offer.md。关键约束与边界青蛙每次只能跳 1 级或 2 级不能跳更多跳法按顺序区分例如 n3 时12与21算两种不同跳法边界条件n1 时只有 1 种跳法跳 1 级n2 时有 2 种跳法11 或直接跳 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 稍大如 n40时计算量将膨胀到数十亿次在面试机试环境中会严重超时因此朴素递归只适合帮助理解递推关系不适合作为提交答案。解法二直接循环——从顶向下改为自底向上原题给出的第二种实现用三个变量滚动更新把递归树变成了线性递推是面试中最推荐的写法之一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;统一处理了 n0、1、2 的边界n0 时返回 0虽然题目通常从 n≥1 讨论但这样写让函数更健壮。数列对照n1234567f(n) 跳法数123581321可以看到数列 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)1f(2)2f(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)是本题的最优解也再次验证了先找规律、再编码的做题思路。复杂度对比与面试要点总结解法时间空间适用场景朴素递归O(2^n)O(n)栈深仅用于理解递推不推荐提交循环迭代滚动变量O(n)O(1)面试标准答案斐波那契模板二刷写法O(n)O(1)面试标准答案代码更简洁变态跳台阶通项 2^(n-1)O(log n)O(1)变体题最优解面试中被问到本题时建议按以下路径作答可以清晰展示思路层次先说明递推关系f(n) f(n-1) f(n-2)边界f(1)1、f(2)2指出朴素递归存在大量重复子问题时间复杂度指数级不可取给出滚动变量的迭代写法说明其 O(n) 时间、O(1) 空间的优势点明本质是斐波那契数列变种并主动延伸如果一次可以跳任意级的变体答案为 2^(n-1)展示思维的广度。系列学习指引本题完整题解与代码注释见 08-剑指offer.md全集汇总见 剑指offer全集.md想按题号顺序系统刷完 67 道题可先阅读系列导读该专栏题目顺序与牛客网《剑指 Offer》专题保持一致若对递推与 DP 状态设计还不熟练可先补算法基础中的复杂度概念再通过动态规划专题的字符匹配类题目练习拆解子问题、画表找状态的方法高频面试题中斐波那契类递推与排序等基础同样重要可参考高频算法题按频率针对性复习。赞分享教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载相关推荐InterviewGuide 剑指 Offer 第 8 题「跳台阶」详解从朴素递归到斐波那契数列滚动迭代InterviewGuide 剑指 Offer 第 8 题「跳台阶」详解从朴素递归到斐波那契数列滚动迭代 本文以 InterviewGuide 仓库《带你快速文档教程知识库剑指Offer No7斐波那契数列 —— 递归、滚动数组与二分幂全解法剖析InterviewGuide 刷题笔记剑指Offer No7斐波那契数列 —— 递归、滚动数组与二分幂全解法剖析InterviewGuide 刷题笔记 本篇是《InterviewGuide》中教程剑指 Offer No7 斐波那契数列三种解法从递归到滚动数组附跳台阶与矩阵覆盖变种实战剑指 Offer No7 斐波那契数列三种解法从递归到滚动数组附跳台阶与矩阵覆盖变种实战 导读 本文是「带你快速刷完 67 道剑指 Offer」系列的第文档教程知识库上一篇探索Nintendo Switch大气层1.7.1三层架构定制系统的技术深度解析下一篇kill-doc浏览器脚本技术架构解析文档下载自动化的前端实现方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
复杂度详解)
