Last Updated on 2022-12-12 by Clay
題目
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:
Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps
Example 2:
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
Constraints:
1 <= n <= 45
題目會給定一個 n 階的樓梯，我們一次能以『一步』或『兩步』登上樓梯。最後，我們要返回我們可以採取了所有爬法的數目。
比方說一個兩階的樓梯，我們就分別有『一階 + 一階』，以及『一次爬兩階』這兩種爬法。
解題思路
遞迴加總
這題我一開始的解法是暴力解，使用 DFS 算出每種變化。但後來觀察階梯數量跟爬法數量的增長規律，發現固定是 n 階樓梯解法 = n-1 階樓梯解法 + n-2 階樓梯解法。
也有找到簡單的數學推導，但並非我想到的，所以在這邊就不列了。
遞迴加總 複雜度
| Time Complexity | O(n) |
| Space Complexity | O(1) |
C++ 範例程式碼
class Solution {
public:
int climbStairs(int n) {
// Base case
if (n == 1) {
return 1;
}
// Init
int n1 = 1;
int n2 = 2;
// Recursive sum
for (int i=2; i<n; ++i) {
int temp = n2;
n2 = n1 + n2;
n1 = temp;
}
return n2;
}
};Python 範例程式碼
class Solution:
def climbStairs(self, n: int) -> int:
# Base case
if n == 1:
return 1
# Init
n1 = 1
n2 = 2
# Recursive sum
for i in range(2, n):
n1, n2 = n2, n1+n2
return n2