递归

和上题类似，第n阶的可能为跳到第n-1阶和第n-2阶两种情况所有的可能加起来。其结构和斐波那契数列一样，只是开始的两个数字为：1 和 2

传统形式

时间复杂度为
空间复杂度为

public class Solution {
    public int JumpFloor(int n) {
        if (n == 1) return 1; 
        if (n == 2) return 2;
        return JumpFloor(n - 1) + JumpFloor(n - 2);
    }
}

优化存储空间

形式1

时间复杂度为
空间复杂度为

public class Solution {
    public int JumpFloor(int target) {
        int a = 1, b = 1;
        for (int i = 1; i < target; i++) {
            a = a + b;
            b = a - b;
        }
        return a;
    }
}

形式2

时间复杂度为
空间复杂度为

public class Solution {
    public int JumpFloor(int target) {
        if(target == 1) return 1;
        if(target == 2) return 2;
        int sum = 2;
        int a0 = 1;
        for(int i =3; i <= target; i++){
            sum = sum + a0;
            a0 = sum - a0;
        }
        return sum;
    }
}