題型解說
這是一題難度為簡單的題目
需要設計一個方法,此方法會傳入一個整數 n,這個 n 代表的階梯的數量
如果一次只能走 1 個階梯或 2 個階梯,回傳要到達第 n 個階梯有幾種走法
範例:
n = 1,則回傳 1,因為只有一個階梯,也只能選擇走 1 個階梯
n = 2,則回傳 2,因為可以選擇走兩次 1 個階梯或是一次走 2 個階梯
n = 3,則回傳 3,因為可以選擇
- 走三次 1 個階梯
- 第一次走 1 個階梯,第二次走 2 個階梯
- 第一次走 2 個階梯,第二次走 1 個階梯
解題思路
其實這一題跟之前的 [LeetCode] #276 Paint Fence 解題 思路一樣
第 n 階的走法數量就是 n - 1 階的數量 + n - 2 階的數量
為什麼會這麼說呢?因為題目規定一次的階梯數只能是 1 或 2
所以最後一步只能由 n - 1 走一個階梯 或 n - 2 走兩個階梯,沒有第三種選擇了
既然如此,只要算出 (n - 1) - 1 + (n - 1) - 2 的數量就可以知道 n - 1 的數量
n - 2 的數量也同樣如此,那就只需要跑一次迴圈就好
程式碼
Java
class Solution {
public int climbStairs(int n) {
if (n < 3) {
return n;
}
int[] temp = new int[n];
temp[0] = 1; // n = 1 只會有一種走法,就直接寫死
temp[1] = 2; // n = 2 只會有兩種走法,一樣寫死
for (int i = 2; i < n; i++) {
temp[i] = temp[i - 1] + temp[i - 2]; // 之後計算每一個階梯的走法數量
}
return temp[n - 1]; // 回傳最後結果就好
}
}