题目：
image.png
仔细一思考，首先1阶和2阶已经是确定的，3阶及以上分成两种情况：
1、爬完它的上一台阶，再爬一阶
2、爬完它的上两个台阶，再爬两阶
所以，本质上，这就是个斐波那契数列。
我迅速写了个递归，一提交，超出时间限制，一分析果然，这么递归，同一个数字，会重复计算好多次
image.png
然后优化了代码，以下是最终版：
class Solution {
public:
int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int tmp0 = 0, tmp1 = 0;
for (int i = 1; i <= n; i++) {
if (i == 1) tmp0 = 1;
else if (i == 2) tmp1 = 2;
else {
tmp1 = tmp0 + tmp1;
tmp0 = tmp1 - tmp0;
}
}
return tmp1;
}
};
提交结果：通过。执行用时：8ms。
image.png
网友评论