var climbStairs = function (n) {
if (n <= 3) return n; // 因為當 n <= 3 的時候答案剛好就是自己本身
return climbStairs(n - 1) + climbStairs(n - 2);
};
但這樣寫… 超時了🥲
動態規劃
這種方法的時間複雜度是 O(n)，因為只需一次循環完成計算。
空間複雜度是 O(1)，因為只需要常數空間來存儲變量 a 和 b。這樣就能有效地解決問題並節省計算資源。
var climbStairs = function (n) {
if (n <= 3) return n; // 當 n 小於等於 3 時，方法數就是 n
let a = 2,
b = 3; // 初始化前兩步的結果
for (let i = 4; i <= n; i++) {
// 從第 4 步開始計算
let c = a + b; // 第 i 步的方法數是前兩步方法數之和
a = b; // 更新 a 和 b，使它們分別表示最新的兩步
b = c;
}
return b; // 最後 b 會是到達第 n 步的方法數
};
DOJO004
