算法（二十六）

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

• 递归实现

public int jumpFloor(int n){ 

    if(n<=2) return n; 

    return jumpFloor(n-1)+jumpFloor(n-2); 

}

• 非递归实现

public int jumpFloor(int n){

     if(n<=2) return n;

     int jumpone = 2;

     int jumptwo = 1;

     int sum = 0;

     for(int i=3; i<=n; i++){

        sum=jumpone + jumptwo；

        jumptwo=jumpone;

        jumpone=sum;

     } 

     return sum;

}

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

• 递归实现

public int jumpFloor(int n){ 

    if(n<=2) return n; 

    return 2 * jumpFloor(n-1); 

}

• 非递归实现

public int jumpFloor(int n){

     if(n<=2) return n;

     int jumpone = 2;

     int sum = 0;

     for(int i=3; i<=n; i++){

        sum=2*jumpone；

        jumpone = sum;

     } 

     return sum;

}