爬樓梯問題：動態規劃與斐波那契的巧妙結合

問題描述

假設你正在爬樓梯，需要爬 n 階才能到達樓頂。每次你可以爬 1 或 2 個臺階。求有多少種不同的方法可以爬到樓頂？

示例：

• n = 2 → 輸出 2（1階+1階 或 2階）
• n = 3 → 輸出 3（1階+1階+1階、1階+2階、2階+1階）

約束：1 ≤ n ≤ 45

---

解題思路

爬樓梯問題本質是斐波那契數列的變種。關鍵洞察：

• 到達第 n 階的最后一步有兩種選擇：
  • 從第 n-1 階爬 1 階
  • 從第 n-2 階爬 2 階
• 因此，狀態轉移方程為：
  dp[n] = dp[n-1] + dp[n-2]

邊界條件

• dp[0] = 1（沒有臺階時視為一種方法）
• dp[1] = 1（爬 1 階只有一種方法）

---

解法分析

1. 記憶化搜索（自頂向下）

通過遞歸+緩存避免重復計算，時間復雜度 $O(n)$，空間復雜度 $O(n)$（遞歸棧深度+緩存數組）。

class Solution {int[] arr = new int[46]; // 緩存數組（n最大為45）public int climbStairs(int n) {return f(n);}private int f(int n) {if (arr[n] != 0) return arr[n]; // 命中緩存if (n == 0 || n == 1) return 1; // 邊界條件arr[n] = f(n-1) + f(n-2); // 遞歸計算并緩存return arr[n];}
}

優勢：

• 直接模擬問題描述，邏輯清晰
• 避免重復計算，效率較純遞歸大幅提升

局限：

• 遞歸調用棧可能溢出（盡管本題 n≤45 安全）

---

2. 動態規劃（自底向上）

迭代計算，消除遞歸開銷。時間復雜度 $O(n)$，空間復雜度 $O(n)$。

class Solution {public int climbStairs(int n) {if (n <= 1) return 1;int[] dp = new int[n+1];dp[0] = 1;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
}

---

3. 空間優化動態規劃（最優解）

僅需保存前兩個狀態，空間復雜度優化至 $O(1)$。

class Solution {public int climbStairs(int n) {if (n <= 1) return 1;int a = 1, b = 1;for (int i = 2; i <= n; i++) {int c = a + b;a = b;b = c;}return b;}
}

優勢：

• 空間效率最高（常數空間）
• 運行速度最快（無遞歸和數組操作開銷）

---

數學視角：斐波那契數列

爬樓梯問題等價于斐波那契數列：

臺階數 n	0	1	2	3	4	5
方法數	1	1	2	3	5	8

可直接套用斐波那契通項公式（但浮點運算可能有精度問題）：

public int climbStairs(int n) {double sqrt5 = Math.sqrt(5);return (int) ((Math.pow((1+sqrt5)/2, n+1) - Math.pow((1-sqrt5)/2, n+1)) / sqrt5);
}

注意：通項公式在 n>45 時可能因浮點精度失效，迭代解法更可靠。

---

總結與對比

方法	時間復雜度	空間復雜度	適用場景
記憶化搜索	$O(n)$	$O(n)$	遞歸思路清晰
動態規劃	$O(n)$	$O(n)$	無棧溢出風險
優化動態規劃	$O(n)$	$O(1)$	最優解，推薦使用
通項公式	$O(1)$	$O(1)$	理論價值高，精度受限

關鍵點：

1. 狀態定義：dp[n] 表示到達第 n 階的方案數
2. 轉移方程：dp[n] = dp[n-1] + dp[n-2]
3. 邊界處理：dp[0]=1, dp[1]=1

面試技巧：先給出遞歸思路，再逐步優化到動態規劃，最后給出空間優化版本，展示算法優化能力！