剑指 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;
}
};
Links: sword-offer-10-2