n个台阶，每次可以走一步或者两步，总共有多少种走法。
第一感觉想到的是递归，n为1的时候1种，2的时候2中。其他时候就是 fun(n) = fun(n-1) + fun(n-2);递归的代码很简单。如下
class Solution {
public:
int climbStairs(int n) {
if (n == ) return ;
if (n == ) return ;
if (n == ) return ;
else
return climbStairs(n-) + climbStairs(n-);
}
};
但是超时了。看了tag提示DP。于是就分分钟改为DP
class Solution {
public:
int climbStairs(int n) {
if (n == ) return ;
if (n == ) return ;
if (n == ) return ;
vector<int> ans(n);
ans[] = ; ans[] = ;
for (int i = ; i < n; ++i)
{
ans[i] = ans[i-] + ans[i-];
}
return ans[n-];
}
};
果断AC。