跳台阶

一只青蛙一次可以跳上一级台阶，也可以跳上两级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）

青蛙每次只有两种跳法：一阶或二阶，假定第一次跳的是一阶，那么剩下的是 n - 1 个台阶，总的跳法是 f(n - 1)

假定第一次跳的是二阶，那么剩下的是 n - 2 个台阶，跳法是 f(n - 2)

通过实际情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2

可以发现最终得出的是一个斐波那契数列：

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

递归会影响效率，可以使用迭代

public int JumpFloor(int target) {

    if(target == 1 || target == 2) {
        return target;
    }

    // 第一阶和第二阶考虑过了，初始当前台阶为第三阶，向后迭代
    // 思路：当前台阶的跳法总数 = 当前台阶后退一阶的台阶的跳法总数 + 当前台阶后退二阶的台阶的跳法总数

    // 当前台阶的跳法总数
    int jumpSum = 0;

    // 当前台阶后退一阶的台阶的跳法总数（初始值当前台阶是第三阶）
    int jumpSumBackStep1 = 2;

    // 当前台阶后退二阶的台阶的跳法总数（初始值当前台阶是第三阶）
    int jumpSumBackStep2 = 1;

    for(int i = 3; i <= target; i++) {
         // 这一次迭代的跳法总数
        jumpSum= jumpSumBackStep1 + jumpSumBackStep2;
        // 下一次迭代后退两阶，相当于这一次迭代后退一阶
        jumpSumBackStep2 = jumpSumBackStep1;
        // 下一次迭代后退一阶，相当于这一次迭代跳法总数
        jumpSumBackStep1 = jumpSum;                   
    }
    return jumpSum;
}