You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
思路:
最简单的DP问题:递归+查表
代码:
int climbStairs(int n) {
vector<int> memo(n+, -);//忘了在memo[0]没有意义的时候,数组初始大小加一。。。
return climb(n, memo);
} int climb(int n, vector<int>& memo){//忘了加&,就会Time Limit Exceeded
if(n < ){
return -;
}
else if(n <= ){
memo[n] = n;
return n;
} if (memo[n-] == -)
memo[n-] = climb(n-, memo);//修改了递归函数名之后没有更改其他函数体中的引用
if(memo[n-] == -)
memo[n-] = climb(n-, memo);
//return memo[n-1] + 2*memo[n-2];//等等,子问题中好像有重叠
return memo[n-] + memo[n-];
}