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

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

记忆化递归

class Solution {
    private int[] memo;
    public int numWays(int n) {
        // f0=1;//0
        // f1=1;
        // f2=f1+f0;//1
        // f3=f2+f1;
        // f4=f2+f3;
        memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return jump(n);
    }
    private int jump(int n) {
        if (memo[n] != -1) {
            return memo[n];
        }//用到缓存
        if (n == 1 || n == 0) {
            return 1;
        }
        memo[n] = (jump(n - 1) + jump(n - 2)) % 1000_000_007;
        return memo[n];
    }
}

时间复杂度O(n)，空间复杂度O(n)。

动态规划1

      //动态规划 
     public int numWays(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 2] + dp[i - 1]) % 1000_000_007;
        }
        return dp[n];
    }

时间复杂度O(n)，空间复杂度O(n)。
https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/solution/mian-shi-ti-10-ii-qing-wa-tiao-tai-jie-wen-ti-dong/

动态规划2

    public int numWays(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        int pre = 1, cur = 2;
        for (int i = 3; i <= n; i++) {
            int tmp = (pre + cur) % 1000_000_007;
            pre = cur;
            cur = tmp;
        }
        return cur;
    }

O(1)空间复杂度的动态规划。