描述

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

数据范围：1<=n<=40

思路1：斐波那契数列

分治法：从上往下分治递归

1. 假设n=5
2. 最后一次可以跳1级，也可以跳2级，因此计算跳到第4级和第3级的路径之和即可：f(4)+f(3)

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

思路2：递归+记忆

思路1包含多次重复计算

由于n<=40，因此可以创建长度为40的数组，记录f(n)的值，避免重复递归计算

public class Solution {
    int[] tmp = new int[40];
    public int jumpFloor(int target) {
        if(target == 1 || target == 2) {
            return target;
        }
        if(tmp[target] != 0) {
            return tmp[target];
        }
        tmp[target] = jumpFloor(target - 1) + jumpFloor(target -2);
        return tmp[target];
    }
}

思路3：动态规划

如上图，可以从下往上合并。

1. 先计算f(2)=f(1)+f(0)
2. 再计算f(3)=f(2)+f(1)
3. 再计算f(4)=f(3)+f(2)
4. 只需要存储两个变量即可

public class Solution {
    public int jumpFloor(int target) {
        int a = 1;
        int b = 1;
        int c = 1;
        for(int i = 2; i <= target; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}