<div>
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
<pre>Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps </pre>
Example 2:
<pre>Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step </pre>
Constraints:
1 <= n <= 45
</div>
题目大意：
爬楼梯的方法数。一次可以爬一级或二级
解题思路：
DP的经典题
递归式
1
dp[n] = dp[n - 1] + dp[n - 2]
解题步骤：
N/A
注意事项：
- 递归式含两个前状态，所以用两个变量。Python的优势是可以同时赋值，所以不需要用临时变量
Python代码：
1
2
3
4
5
6# dp[n] = dp[n - 1] + dp[n - 2]
def climbStairs(self, n: int) -> int:
prev, cur = 1, 1
for i in range(2, n + 1): # 4
cur, prev = cur + prev, cur # 5, 3
return cur
算法分析：
时间复杂度为O(n)，空间复杂度O(1)
