题目主要信息

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

2、进阶：空间复杂度 O(1) ， 时间复杂度 O(1)

方法一：暴力

具体方法

设dp[i]表示当前第i个台阶一共有多少跳法，题目要求的就是dp[target]

若已经跳到了第 n 个台阶，前一步可以从哪些台阶到达呢？

上一步跳 1 步到达第 n 个台阶，说明上一步在第 n-1 个台阶。已知跳到第n-1个台阶的方法数为dp[n-1]

上一步跳 2 步到达第 n 个台阶，说明上一步在第 n-2 个台阶。已知跳到第n-2个台阶的方法数为dp[n-2]

...

上一步跳 n 步到达第 n 个台阶，说明上一步在第 0 个台阶。已知跳到 第0个台阶的方法数为dp[0]

那么总的方法数就是所有可能的和。也就是dp[n] = dp[n-1] + dp[n-2] + ... + dp[0]

显然初始条件dp[0] = dp[1] = 1

所以我们就可以先求dp[2]，然后dp[3]...dp[n-1]， 最后dp[target]

Java代码

public class Solution {
    public int jumpFloorII(int target) {
        int dp[] = new int[target+1];
        dp[0] = dp[1] = 1;
        for (int i=2; i<=target; ++i) {
            for (int j=0; j<i; ++j) {
               dp[i] += dp[j];
            }
        }
        return dp[target];
    }
}

复杂度分析

• 时间复杂度：$O(n^2)O(n^2)$，两层for循环
• 空间复杂度：$O(n)O(n)$，一个dp数组存结果

方法二：使用数学公式

具体方法

我们可以通过一些实例寻找规律。

dp[0] = dp[1] = 1

dp[2] = 2 = 2^1

dp[3] = 4 = 2^2

dp[4] = 8 = 2^3

...

dp[n] = 2^(n-1)

Java代码

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

复杂度分析

• 时间复杂度：$O(1)O(1)$，一次位运算
• 空间复杂度：$O(1)O(1)$，一个保存结果的临时变量

方法三：递归

具体方法

方法类似跳台阶问题

dp[target] = dp[target-1]+...+dp[0]

而其中的每一个dp[target-1] = dp[target-2]+...+dp[0]

Javad代码

public class Solution {
    public int jumpFloorII(int target) {
        if(target<=1)
            return 1;
        int result = 0;
        for(int i=1;i<=target;i++){
            result+=jumpFloorII(target-i);
        }
        return result;
    }
}

复杂度分析

• 时间复杂度：$O(n^2)O(n^2)$，两层循环，每一层后又进行一层循环。
• 空间复杂度：$O(n)O(n)$，递归栈的空间

方法四：递归优化

具体方法

类似跳台阶问题的优化思路

$dp[target]=2\ast dp[target-1]dp[target]\; =\; 2*dp[target-1]$

Java代码

public class Solution {
    public int jumpFloorII(int target) {
        if(target<=1)
            return 1;
        return 2*jumpFloorII(target-1);
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，只有一层递归
• 空间复杂度：$O(n)O(n)$，递归栈最大深度