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

概述

https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/

https://leetcode.com/problems/climbing-stairs/

直接法

class Solution {
public:
    int store[101] = {0};
    int numWays(int n) {
        if (n == 0) return 1;
        if (n == 1) return 1;
        if (store[n] != 0) return store[n] % 1000000007;
        store[n] = numWays(n-1) + numWays(n-2);
        return store[n] % 1000000007;
    }
};

动态规划法

class Solution {
public:
    int numWays(int n) {
        if (n == 0) return 1;
        if (n == 1) return 1;
        if (n == 2) return 2;
        vector<int> dp(n+1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i=3; i <= n; i++) {
            dp[i] = dp[i-1] % 1000000007 + dp[i-2] % 1000000007;
        }
        return dp[n] % 1000000007;
    }
};