2019-03-24 变态跳台阶（递归、动态规划）

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

• 解答：也可以用逆推的思路去想，跳n级台阶，可以从n-1级跳上来，也可以从n-2级跳上来，从n-3级跳上来，依次下去，从第1级跳上去，或直接跳上去，所以，跳n级台阶的方法数相当于其它所有台阶数的方法的总和再加上从0级跳上去，表达式为 f(n) = f(n-1) + f(n-2) +...+ f(2) + f(1) + 1。例如：

当跳1级台阶时，f(1) = 1;

当跳2级台阶时，f(2) = f(1) + 1 = 2;

当跳3级台阶时，f(3) = f(2) + f(1) + 1 = 4;

当跳4级台阶时，f(4) = f(3) + f(2) + f(1) + 1 = 8;

即：

f(n) = f(n-1) + f(n-2) +...+ f(2) + f(1) + 1

f(n-1) = f(n-2) +...+ f(2) + f(1) + 1

===》》 f(n) - f(n-1) = f(n-1) ===》》f(n) = 2 * f(n-1)

    /**
     * 方法1：递归。使用递归需要知道
     * (1)递归结束条件，何时结束
     * (2)以及递归的计算方式
     *
     * @param target
     * @return
     */
    public int JumpFloorII(int target) {
        return loopJump(target);
    }

    public int loopJump(int target) {
        // 递归结束条件
        if (target <= 0) {
            return 0;
        }
        // 递归初始条件
        if (target == 1) {
            return 1;
        }
        return 2*loopJump(target - 1);
    }