跳台阶—2018-6-9

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

---

思考五分钟

解题思路：
要想上n级台阶，那么必须先到n-2或者n-1阶台阶。
可以设到n阶台阶的函数为f(n).
则，当n>2的时候有，f(n)=f(n-1)+f(n-2)
而f(0)=0,f(1)=1,f(2)=2。

这很类似于Fibonacci函数，使用迭代或者递归都可以完成。
迭代实现：

/*
**targrt目标阶数
**fn：到n阶台阶的方法
*/
public int JumpFloor(int target) {
        if(target==0)
            return 0;
        else if(target==1)
            return 1;
        else {
            int f1=1,f2=2,fn=2;
            for(int i=2;i<target;i++){
                fn=f1+f2;
                f1=f2;
                f2=fn;
            }
            return fn;
        }
    }

递归实现：

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