一、题目说明
题目70. Climbing Stairs,爬台阶(楼梯),一次可以爬1、2个台阶,n层的台阶有几种爬法。难度是Easy!
二、我的解答
类似的题目做过,问题就变得非常简单。首先用递归方法计算:
class Solution{
public:
int climbStairs(int n){
if(n==1) return 1;
if(n==2) return 2;
return climbStairs(n-1) + climbStairs(n-2);
}
};
非常不好意思,Time Limit Exceeded
。
那就用dp算法吧:
class Solution{
public:
int climbStairs(int n){
if(n==1) return 1;
if(n==2) return 2;
vector<int>dp;
dp.push_back(1);
dp.push_back(2);
for(int i=2;i<n;i++){
dp.push_back(dp[i-1]+dp[i-2]);
}
return dp[n-1];
}
};
性能:
Runtime: 4 ms, faster than 55.03% of C++ online submissions for Climbing Stairs.
Memory Usage: 8.4 MB, less than 51.47% of C++ online submissions for Climbing Stairs.
三、优化措施
不优化了!