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; d