剑指offer习题---跳台阶

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

 public static int jumpFloor(int target){
        int fn1 = 1;
        int fn2 = 2;
        int res = 0;
        if(target<0){
            return 0;
        }
        if(target<=2){
            return target;
        }
        for (int i=3;i<=target;i++){
            res = fn1 +fn2;
            fn1 = fn2;
            fn2 = res;
        }
        return res;
    }

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

对于N级台阶，可以从N-1 和N-2级的台阶跳上去。所以最后的结果f(n) = f(n-1)+f(n-2);所以只需要考虑到f(n-1)的情况加上到f(n-2)的情况之和。最终迭代到前面最小基数项就可以了。因为有两种跳发，所以最小基数项有两个，即f(1) ,f(2);

变态跳台阶

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

记第n级台阶的跳法有f(n)种：

从第n-1级跳1步，有f(n-1)种；
从第n-2级跳2步，有f(n-2)种;
.........
从第1级跳n步，有f(1)种；
f(n) = f(n-1)+f(n-2)+......+f(1)
f(n-1) = f(n-2)+......+f(1)
相减得：
f(n) = 2f(n-1);
f(n) = 2ⁿ

算法实现
1 递归

public class Solution {  
        public int JumpFloorII(int target) {  
            if (target < 0) {  
                return 0;  
            } else if (target == 1) {  
                return 1;  
            } else {  
                return 2 * JumpFloorII(target - 1);  
            }  
        }  
    }  

2 非递归

public class Solution {  
    public int JumpFloorII(int target) {  
        int jumpFlo = 1;  
        while (--target > 0) {  
            jumpFlo *= 2;  
        }  
        return jumpFlo;  
    }  
}  

3 位移操作

pblic class Solution {  
    public int JumpFloorII(int target) {  
        return  1<<--target;  
    }  
       }