題目連結

題型解說

這是一題難度為簡單的題目

需要設計一個方法，此方法會傳入一個整數 n，這個 n 代表的階梯的數量

如果一次只能走 1 個階梯或 2 個階梯，回傳要到達第 n 個階梯有幾種走法

範例:

n = 1，則回傳 1，因為只有一個階梯，也只能選擇走 1 個階梯
n = 2，則回傳 2，因為可以選擇走兩次 1 個階梯或是一次走 2 個階梯
n = 3，則回傳 3，因為可以選擇

1. 走三次 1 個階梯
2. 第一次走 1 個階梯，第二次走 2 個階梯
3. 第一次走 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]; // 回傳最後結果就好
    }
}