剑指offer 8.跳台阶

时间限制：1秒 空间限制：32768K
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

思路: 典型的斐波那契算法思路,
1.假设当有n个台阶时假设有f(n)种走法。
2.青蛙最后一步要么跨1个台阶要么跨2个台阶,只有这两种情况。
3.当最后一步跨1个台阶时即之前有n-1个台阶，根据1的假设即n-1个台阶有f(n-1)种走法。
4. 当最后一步跨2个台阶时即之前有n-2个台阶，根据1的假设即n-2个台阶有f(n-2 )种走法。
5.显然n个台阶的走法等于前两种情况的走法之和即f(n)=f(n-1)+f(n-2)。
6.找出递推公式后要找公式出口，即当n为1、2时的情况，显然n=1时f(1)等于1，f(2)等于2
7可得公式为:. $f\left(n\right)=\{\begin{array}{cc}1,& \text{n=1}\\ 2,& \text{n=2}\\ f(n-1)+f(n-2),& \text{(n\>2,n为整数)}\end{array}$f(n)=⎩⎪⎨⎪⎧​1,2,f(n−1)+f(n−2),​n=1n=2(n>2,n为整数)​
代码如下:

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