剑指offer面试题[9-1]-跳台阶 Dear 丶 2022-06-13 02:16 126阅读 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; \} \};
还没有评论,来说两句吧...