链接
https://leetcode-cn.com/problems/climbing-stairs/
耗时
解题：5 min 题解：12 min
题意
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
思路
与 剑指 Offer 10- II. 青蛙跳台阶问题 基本相同。
状态 dp[i] 可以从 dp[i-1] 跳一个台阶 转移得到，也可以从 dp[i-2] 跳两个台阶 转移得到，所以状态转移方程如下：
d
p
[
i
]
=
d
p
[
i
−
1
]
+
d
p
[
i
−
2
]
dp[i] = dp[i-1] + dp[i-2]
dp[i]=dp[i−1]+dp[i−2]
时间复杂度：
O
(
n
)
O(n)
O(n)
AC代码
class Solution {
public:
int climbStairs(int n
) {
if(n
< 3) return max(1, n
);
vector
<int> dp(n
+2);
dp
[1] = 1;
dp
[2] = 2;
for(int i
= 3; i
<= n
; ++i
) {
dp
[i
] = dp
[i
-1] + dp
[i
-2];
}
return dp
[n
];
}
};
滚动更新（节省空间）
class Solution {
public:
int climbStairs(int n
) {
if(n
< 3) return max(1, n
);
int pre
= 1, post
= 2;
for(int i
= 3; i
<= n
; ++i
) {
int tmp
= post
;
post
= pre
+post
;
pre
= tmp
;
}
return post
;
}
};
