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

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

方法1 暴力法
用递归暴力求解即可
时间复杂度 O(n^2)
空间复杂度 O(1)

public class Solution {
    public int jumpFloorII(int target) {
        int sum = 1;
        for(int i=1; i<target; i++){
            sum = sum + jumpFloorII(i);
        }
        return sum;
    }
}

方法2 简化法
f[n] = f[n-1] + f[n-2] + ... + f[0]
f[n-1] = f[n-2] + f[n-3] + ... + f[0]
所以 f[n] = 2*f[n-1]
得 f[n] = 2^(n-1)
时间复杂度：O(n)
空间复杂度：O(1)

public class Solution {
    public int jumpFloorII(int target) {
        int result = (int)(Math.pow(2, target-1));
        return result;
    }
}