题解 | #跳台阶扩展问题#

思路
思路：假设现在台阶数是n。
假设第一步跳了1，那么剩下的n-1步的跳法数即为jumpFloorII(n-1)
假设第一步跳了2，那么剩下的n-2步的跳法数即为jumpFloorII(n-2)
假设第一步跳了3，那么剩下的n-2步的跳法数即为jumpFloorII(n-3)
. . . . .
. . . . .
假设第一步跳了n，那么剩下的n-2步的跳法数即为jumpFloorII(n-n)
所以如果跳n阶台阶，那么总共跳法就是前n-1的跳法之和。
不需要考虑什么先跳1步，然后再跳2步，再跳1步....然后再跳多少多少步，因为在递归的时候jumpFloorII(n-1)或jumpFloorII(n-2)也是按照
假设第一步跳1，假设第一部跳2...，那么这样就完美的包含了所有随机组合的出现.

结果
运行时间：19ms
占用内存：10700KB

代码

public int jumpFloorII(int target) {
        if (target < 1) return 1;

        int sum = 0;
        // 计算当前target的前target-1的方法总和，便是target的跳法数
        /*for (int i = 0; i < target; i++) {
            // 计算前target - 1的跳法总和
            sum+=jumpFloorII(i);
       }*/

        // 计算当前target的前target-1的方法总和，便是target的跳法数
        for (int i = 1; i<target ; i++) {
            // 递归求，第一次跳1步 | 2步 | 3步 ... target - 1步 的所有方法总和
            // 这里不能求第一次跳target步，因为这样会使方法一直循环死递归，解决方法就是返回值加1，因为第一次跳target步，仅一种方法
            sum+=jumpFloorII(i);
        }

        return sum + 1;
    }