#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
class Solution {
private:
vector<int> memo;
int calcWays(
int n){
if(n ==
0 || n ==
1)
return 1;
if(memo[n] == -
1)
memo[n] = calcWays(n -
1) + calcWays(n -
2);
return memo[n];
}
public:
int climbStairs(
int n) {
assert(n >
0);
memo =
vector<int>(n +
1, -
1);
return calcWays(n);
}
};
int main() {
cout << Solution().climbStairs(
38) << endl;
return 0;
}
这里注意保存已经计算过的值，不然提交leetcode会超时
