剑指Offer 10- II 青蛙跳台阶问题

mario 2020年09月13日 78次浏览

前言

独立做出的第二个题目,哈哈哈,用到了递归,结果超时了,遂考虑动态规划做法。

分析题目

image.png

解法1 - 递归

class Solution {
    public int numWays(int n) {
        return jump(n);
    }
    //递归
    private int jump(int n) {
        if (n == 0) return 1;
        if (n < 0) return 0;
        return jump(n - 1) + jump(n - 2);
    }
}

代码简洁,但会有大量重复的计算。超时了T-T。

解法2 - 动态规划

class Solution {
    public int numWays(int n) {
        return jump2(n);
    }
    //dp
    private int jump2(int n) {
        if (n == 0) return 1;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
        }
        return dp[n];
    }
}

时间和空间复杂度都是O(N)

解法3 - 动态规划优化

class Solution {
    public int numWays(int n) {
        return jump3(n);
    }
    //dp优化
    private int jump3(int n) {
        if (n == 0) return 1;
        int pre, last, tmp = 0;
        last = 1;
        pre = 1;
        for (int i = 2; i <= n; i++) {
            tmp = (last + pre) % 1000000007;
            last = pre;
            pre = tmp;
        }
        return pre;
    }
}

不用分配数组,空间复杂度降到O(1)

解法4 - 记忆化递归

题解提到的解法,在解法1的基础上加个长度为n的数组,保存f(0)到f(n),计算f(x)前查询该数组,这样就避免了重复的计算。