009 变态跳台阶

1.题目

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

 

2.思路

　　这里主要有两种思路，我感觉第二种更好理解一点。

　　1.

　　假设：f(n)表示：n个台阶第一次1,2,...n阶的跳法数;

　　若第一次跳了1阶，则还剩n-1阶，
　　假设：f(n-1)表示：n-1个台阶第一次1,2,...n-1阶的跳法数;
　　若第一次跳了2阶，则还剩n-2阶，
　　假设：f(n-2)表示：n-1个台阶第一次1,2,...n-2阶的跳法数;
   　　 // ...
　　把所以可能的情况（第一次可能跳1,2,...,n阶）加起来：
　　可以求出：f(n) = f(n-1) + f(n-2) + ... + f(1)
　　递归：f(n-1) = f(n-2) + ... + f(1)
　　可以求出：f(n) = 2*f(n-1)
　　2.
　　每个台阶可以跳或者不跳

3.程序

package first;

public class JumpFloorII {
    public static void main(String[] args){
        //
        int a=JumpFloorII(3);
        System.out.println(a);
        //
        int b=JumpFloorII2(3);
        System.out.println(b);
        //
        int c=JumpFloorII3(3);
        System.out.println(c);
        //
        int d=JumpFloorII4(3);
        System.out.println(d);
    }

    public static  int JumpFloorII(int target) {
        if(target<=0)
            return 0;
        return 1<<(target-1);
    }

    public static int JumpFloorII2(int target){
        if(target<=0){
            return 0;
        }else if(target==1){
            return 1;
        }else
            return 2*JumpFloorII2(target-1);
    }

    public static int JumpFloorII3(int target){
        if (target <= 0) return 0;
        return (int) Math.pow(2, target - 1);
    }

    public static int JumpFloorII4(int target){
        if (target==0)
            return 0;
        if (target==1)
            return 1;
        int a=1;   //第一次的方法
        int b=2;   //第二次的方法
        for(int i=2;i<=target;i++){
            b=2*a;  //2*上一次的方法
            a=b;    //将值传递，然后继续下一步计算
        }
        return b;
    }


}