LeetCode Dynamic Programming_70. Climbing Stairs(Easy)

題目描述：

你正在爬樓梯。樓梯有 n 階，每次你可以爬 1 階或 2 階。你想要到達樓梯的頂部，有多少種不同的方法可以達到頂部？

可以使用動態規劃的方法來解決這個問題，建立一個長度為 n+1 的數組 dp，其中 dp[i] 表示爬到第 i 階樓梯的不同方法數。

我們可以初始化 dp[0] 為 1，因為爬到第 0 階樓梯的方法只有一種，就是不動。同樣地，dp[1] 也為 1，因為爬到第 1 階樓梯的方法只有一種，就是爬一階。接下來，我們可以使用遞歸關係式來計算 dp[i]，即：

dp[i] = dp[i-1] + dp[i-2]

這是因為要到達第 i 階樓梯，我們可以從第 i-1 階樓梯爬一階，或者從第 i-2 階樓梯爬兩階。這樣我們就可以不斷地更新 dp 數組，直到計算出 dp[n]，它表示到達頂部的不同方法數。

從 n > 2 開始，到達 n - 1 階和 n - 2 階的⽅方法數都已知了了：

• n - 1 階到達第 n 階只有⼀一種⽅方法：走⼀一次⼀一步
• n - 2 階到達第 n 階有兩兩種⽅方法：走兩兩次⼀一步、走⼀一次兩兩步。但第⼀一種⽅方法和 n - 1 階到 n 階重複，不予考慮

承上，到 (n - 1) 及 (n - 2) 後，可以到達 n 的可能選項已被固定，0 -> n ⽅方法數 = 0 -> (n - 1) ⽅方法數 + 0 -> (n - 2) ⽅方法數

Dynamic Programming(DP) 常⽤用思維：a -> b 只有⼀一個選項，代表通往終點的可能選項已經被固定住了了。因為可能選項已經被固定住了了，程式只需計算到前⼀一步。

Dynamic Programming： 每次的運算結果，都是基於此前以同⼀一個邏輯運算的結果 

-> f(n) = f(n - 1) + f(n - 2)

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) {
            return 1; // 當 n <= 1 時，只有一種方法
        }
        
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        dp[1] = 1;
        
        for (int i = 2; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
};




時間複雜度: O(n)

空間複雜度: O(1)