Description
你正在爬一個有
n階的樓梯，每次可以爬 1 階或 2 階。請問有多少種不同的方式可以爬到頂端？
Example:
Input: n = 3 Output: 3
Intuition#
到第 n 階的方法數 = 到第 n-1 階 + 到第 n-2 階，本質上就是費氏數列。
- 每一步只能選 1 或 2，所以到達第
i階只能從i-1或i-2來 - 狀態轉移：
dp[i] = dp[i-1] + dp[i-2] - 只依賴前兩個狀態，可以用兩個變數取代陣列
Approaches#
1: Top-Down Memoization#
- 概念: 遞迴 + 記憶化，從
n往下拆解到 base case - 時間複雜度:
O(n) - 空間複雜度:
O(n)
class Solution {
fun climbStairs(n: Int): Int {
val memo = IntArray(n + 1) { -1 }
fun dp(i: Int): Int {
if (i <= 1) return 1
if (memo[i] != -1) return memo[i]
memo[i] = dp(i - 1) + dp(i - 2)
return memo[i]
}
return dp(n)
}
}⭐2: Bottom-Up with Rolling Variables#
- 概念: 自底向上迭代，只用兩個變數追蹤前兩個狀態，空間最優
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun climbStairs(n: Int): Int {
var prev2 = 1
var prev1 = 1
for (i in 2..n) {
val cur = prev1 + prev2
prev2 = prev1
prev1 = cur
}
return prev1
}
}🔑 Takeaways#
- Pattern: 費氏數列變體 — 只依賴前兩個狀態的線性 DP
- 關鍵技巧: 當 DP 只依賴固定數量的前幾個狀態時，可以用滾動變數把空間從
O(n)降到O(1)