剑指offer面试题[9-1]-跳台阶

Dear 丶 2022-06-13 02:16 166阅读 0赞

## 题目描述 ##

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

分析：如果台阶数为0，就有0种跳法；如果台阶数为1，那么就有1种跳法；如果台阶数为2，那么就有2种跳法；如果台阶数为3，则有3种跳法。当台阶数小于等于3的时候，列举法都可以列举出来，当台阶数为4的时候，问题就开始变得复杂了，我们可以这样想，由于一次跳的台阶数只能是1或者2，那么要跳到第4个台阶，只有两种可能，要么从第2个台阶跳2个台阶到第4个，要么就是从第3个台阶跳1个台阶到第4个。所以跳到第4个台阶的跳法就应该等于跳到第2个台阶的总方法加上跳到第3个台阶的总方法，即f(4)=f(2)+f(3)。要想跳到第5个台阶，同样的道理，要么是从第3个台阶直接跳2个台阶到5个台阶，要么从第4个台阶直接跳1个台阶到第5个台阶，所以跳到第5个台阶的跳法就应该等于跳到第3个台阶的总方法加上跳到第4个台阶的总方法，即f(5)=f(4)+f(3)。依次内推方法。。。自己在纸上画下很直观的可以看出来，所以这题的思想其实就是裴波那契数列。但是用递归的方法的话就会过于复杂，可能运行会超时。

class Solution \{  
public:  
    int jumpFloor(int number) \{

int result\[3\]=\{0,1,2\};

if(number<3)

return result\[number\];

int frontStage1=1;          //frontStage1与frontStage2分别记录当前台阶前面两次总的跳的方法

int frontStage2=2;          //因为下面for循环是从3开始的，初始化为frontStage1=1，frontStage2=2。

int StageNumber;          //定义总的跳发次数

for(int i=3;i<=number;i++)

\{

StageNumber=frontStage1+frontStage2;

frontStage1=frontStage2;            //更新frontStage1与frontStage2，使其成为下次计算跳到第n个台阶的前面两种方法

frontStage2=StageNumber;        //即f(n)=f(n-1)+f(n-2)

\}

return StageNumber;

\}  
\};

发表评论取消回复

表情：

评论列表（有 0 条评论，166人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指Offer-跳台阶

跳台阶题目描述: 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。解题思路：其实仔细分析一下，可以发现

叁歲伎倆/ 2022年08月04日 12:50/ 0 赞/ 149 阅读

相关剑指offer面试题[9-1]-跳台阶

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。分析：如果台阶数为0，就有0种跳法；如果台阶数为1，

Dear 丶/ 2022年06月13日 02:16/ 0 赞/ 167 阅读

相关【剑指offer】面试题：变态跳台阶

完整代码地址 [完整代码地址][Link 1] 题目一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法

ゝ一纸荒年。/ 2022年06月12日 07:22/ 0 赞/ 195 阅读

相关【剑指offer】面试题：跳台阶

完整代码地址 [完整代码地址][Link 1] 题目一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。思路很

矫情吗；*/ 2022年06月12日 07:21/ 0 赞/ 272 阅读

相关剑指Offer | 跳台阶

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

雨点打透心脏的1/2处/ 2022年05月25日 11:20/ 0 赞/ 173 阅读

相关剑指offer：跳台阶

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。跳台阶还是个斐波那契数列 c

冷不防/ 2022年04月14日 05:13/ 0 赞/ 206 阅读

相关剑指Offer-跳台阶

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。初步解题思路：这题与[斐波那契数列][

深碍√TFBOYSˉ_/ 2022年03月01日 01:20/ 0 赞/ 189 阅读

相关剑指offer-跳台阶

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。实现思想对于本题，可以从后往前

梦里梦外;/ 2022年02月17日 05:39/ 0 赞/ 174 阅读

相关【剑指offer】跳台阶

题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。题目解析：当只有一节台阶的时候由于每

深碍√TFBOYSˉ_/ 2021年11月09日 14:16/ 0 赞/ 285 阅读

相关剑指offer：跳台阶

试题：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。代码：跳到第n台阶有两种方式，从第n-1

た入场券/ 2021年06月24日 16:00/ 0 赞/ 375 阅读