题目
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析
才开始感觉有点懵，就看一下规律，当台阶只有一级台阶，f(1)=1，当台阶有2级，f(2)=2，当台阶有3级，f(3) = 3,f(4) = 5,依次类推，发现是个斐波拉切数列。 那么，为什么会是这样呢？ 假设要跳到6，有两种，一种是从5跳到5，这个时候，跳到6的方式就是f(5)，另一种是从4跳到6,方法数就是f(4).所以f(6) = f(5) + f(4)，正好是斐波拉切数列。
而传统的斐波拉切数列是0，1，1，2，3，5，8…….按照题意，本题中的数列是0，1，2，3，5，8…，就是0级的时候是0，1级的时候有一种，2级的时候有2中，依次类推。 所以，在前面我先判断一下，0级和1级的时候，都返回1，就能通过，而我用的方式是尾递归
代码
public class offer8 {
public static void main(String[] args) {
// TODO Auto-generated method stub
offer8 offer8 = new offer8();
System.err.println(offer8.JumpFloor(3));
}
public int JumpFloor(int target) {
if (target ==0 || target == 1) {
return 1;
}else{
return Fib(target, 0, 1);
}
}
public int Fib(int n, int a,int b){
if (n == 0) {
return b;
}else{
return Fib(n-1, b, a+b);
}
}
}
但是我觉得更好的解法是，用循环;
public class Solution {
public int JumpFloor(int target) {
if(target < 0)
return -1;
if(target == 0 || target == 1){
return 1;
}
if(target == 2){
return 2;
}
int prePreNumber = 1;
int preNumber = 2;
int result = 0;
for(int i = 3;i<=target;i++){
result = prePreNumber+preNumber;
prePreNumber = preNumber;
preNumber = result;
}
return result;
}
}
