题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法
（先后次序不同算不同的结果）。
思路：用斐波那契思想
只有一级台阶:只有1种跳法 a.1 f(1)
只有二级台阶:只有2种跳法 a.1 1 b.2 f(2)
只有三级台阶:只有3种跳法 a. 1 1 1 b.1 2 c. 2 1 f(3)
只有四级台级:只有5种跳法 a.1 1 1 1 1 b.1 2 2 c.2 1 2 d 2 2 1 f(5)
以此类推....f(n)=f(n-1)+f(n-2);
方法一：递归 （耗时耗空间）
1 class Solution { 2 public: 3 int jumpFloor(int number) { 4 if(number==0){ 5 return 0; 6 } 7 if(number==1){ 8 return 1; 9 } 10 if(number==2){ 11 return 2; 12 } 13 return jumpFloor(number-1)+jumpFloor(number-2); 14 } 15 };
方法二：循环
思路：利用变量作为中间量，先把1 和 2的阶梯排除掉
1 class Solution { 2 public: 3 int jumpFloor(int number) { 4 if(number==1){ 5 return 1; 6 } 7 if(number==2){ 8 return 2; 9 } 10 int k1=1;//第一台阶 11 int k2=2;//第二台阶 12 int g=0;//中间变量 13 for(int i=3;i<=number;i++){ 14 g=k1+k2; 15 k1=k2; 16 k2=g; 17 } 18 return g; 19 20 } 21 };
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
