Climbing Stairs
•--
Dynamic programming solution using Fibonacci sequence pattern
Calculate number of distinct ways to climb stairs, taking 1 or 2 steps at a time
問題描述
假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？
範例
輸入：n = 2
輸出：2
解釋：有兩種方法可以爬到樓頂。
1. 1 階 + 1 階
2. 2 階
輸入：n = 3
輸出：3
解釋：有三種方法可以爬到樓頂。
1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階
限制條件
1 <= n <= 45
解題思路
找出規律 - 到達第 1 階：1 種方法 - 到達第 2 階：2 種方法 - 到達第 3 階：3
種方法（從第 1 階爬 2 步 + 從第 2 階爬 1 步）
### 空間優化 使用兩個變數儲存前兩個狀態，避免使用額外的陣列空間
解決方案
typescript
/**
* 計算爬樓梯的所有可能方法數
*
* 原理：每一階的方法數等於前兩階方法數的總和
* - 從 n-1 階爬 1 步到達 n 階
* - 從 n-2 階爬 2 步到達 n 階
*/
export function climbStairs(totalStairs: number): number {
// 處理基礎案例
if (totalStairs <= 2) {
return totalStairs;
}
// 初始狀態
let [twoStepsBefore, oneStepBefore] = [1, 2];
// 從第 3 階開始計算
Array.from({ length: totalStairs - 2 }).forEach(() => {
[twoStepsBefore, oneStepBefore] = [
oneStepBefore,
twoStepsBefore + oneStepBefore,
];
});
return oneStepBefore;
}