70. 爬樓梯

描述

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

示例 1

輸入：n = 2
輸出：2
解釋：有兩種方法可以爬到樓頂。

1. 1 階 + 1 階
2. 2 階

示例 2

輸入：n = 3
輸出：3
解釋：有三種方法可以爬到樓頂。

1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階

提示

• 1 <= n <= 45

解題思路

核心分析

這是一道經典的動態規劃入門題目，本質上是斐波那契數列的變形。

問題建模

要到達第n階樓梯，可以從兩個位置到達：

1. 從第(n-1)階爬1步
2. 從第(n-2)階爬2步

因此：f(n) = f(n-1) + f(n-2)

這正是斐波那契數列的遞推關系！

算法實現

方法1：動態規劃（標準解法）

狀態定義：

• dp[i] 表示到達第i階樓梯的方法數
• dp[i] = dp[i-1] + dp[i-2]

邊界條件：

• dp[1] = 1（只有一種方法：爬1步）
• dp[2] = 2（兩種方法：1+1 或 2）

func climbStairs(n int) int {if n <= 2 {return n}dp := make([]int, n+1)dp[1] = 1dp[2] = 2for i := 3; i <= n; i++ {dp[i] = dp[i-1] + dp[i-2]}return dp[n]
}

時間復雜度：O(n)
空間復雜度：O(n)

方法2：空間優化動態規劃（最優解）

由于狀態轉移只依賴前兩個狀態，可以用兩個變量代替數組。

func climbStairsOptimized(n int) int {if n <= 2 {return n}prev2 := 1  // f(1)prev1 := 2  // f(2)for i := 3; i <= n; i++ {curr := prev1 + prev2prev2 = prev1prev1 = curr}return prev1
}

時間復雜度：O(n)
空間復雜度：O(1)

方法3：遞歸 + 記憶化

使用遞歸思路，配合記憶化避免重復計算。

func climbStairsMemo(n int) int {memo := make(map[int]int)return climbStairsMemoHelper(n, memo)
}func climbStairsMemoHelper(n int, memo map[int]int) int {if n <= 2 {return n}if val, exists := memo[n]; exists {return val}result := climbStairsMemoHelper(n-1, memo) + climbStairsMemoHelper(n-2, memo)memo[n] = resultreturn result
}

時間復雜度：O(n)
空間復雜度：O(n)

方法4：數學公式（斐波那契通項公式）

使用貝爾納公式直接計算斐波那契數列第n項。

func climbStairsFormula(n int) int {if n <= 2 {return n}sqrt5 := math.Sqrt(5)phi := (1 + sqrt5) / 2        // 黃金比例psi := (1 - sqrt5) / 2        // 共軛黃金比例// 斐波那契通項公式：F(n) = (φ^n - ψ^n) / √5// 但這里是 F(n+1)，因為我們的序列是 f(1)=1, f(2)=2result := (math.Pow(phi, float64(n+1)) - math.Pow(psi, float64(n+1))) / sqrt5return int(math.Round(result))
}

時間復雜度：O(1)
空間復雜度：O(1)

方法5：矩陣快速冪

使用矩陣快速冪計算斐波那契數列，適合處理大數。

func climbStairsMatrix(n int) int {if n <= 2 {return n}// 轉換矩陣: [[1,1],[1,0]]base := [][]int{{1, 1}, {1, 0}}result := matrixPower(base, n-1)// result * [F(2), F(1)] = [F(n+1), F(n)]return result[0][0]*2 + result[0][1]*1
}func matrixPower(matrix [][]int, n int) [][]int {size := len(matrix)result := make([][]int, size)for i := range result {result[i] = make([]int, size)result[i][i] = 1  // 單位矩陣}base := make([][]int, size)for i := range base {base[i] = make([]int, size)copy(base[i], matrix[i])}for n > 0 {if n&1 == 1 {result = matrixMultiply(result, base)}base = matrixMultiply(base, base)n >>= 1}return result
}func matrixMultiply(a, b [][]int) [][]int {size := len(a)result := make([][]int, size)for i := range result {result[i] = make([]int, size)for j := 0; j < size; j++ {for k := 0; k < size; k++ {result[i][j] += a[i][k] * b[k][j]}}}return result
}

時間復雜度：O(log n)
空間復雜度：O(1)

復雜度分析

方法	時間復雜度	空間復雜度	優缺點
標準DP	O(n)	O(n)	思路清晰，易理解
空間優化DP	O(n)	O(1)	最實用的解法 ?
記憶化遞歸	O(n)	O(n)	自頂向下，遞歸棧開銷
數學公式	O(1)	O(1)	最快，但有精度問題
矩陣快速冪	O(log n)	O(1)	適合大數，復雜度低

核心要點

1. 斐波那契本質：問題等價于求斐波那契數列第(n+1)項
2. 狀態轉移：每個狀態只依賴前兩個狀態
3. 空間優化：可以用O(1)空間代替O(n)空間
4. 邊界處理：n=1和n=2的特殊情況

數學推導

遞推關系證明

設 f(n) 表示到達第n階樓梯的方法數：

遞推關系：

f(n) = f(n-1) + f(n-2)  (n ≥ 3)

初始條件：

f(1) = 1
f(2) = 2

證明：
要到達第n階，只能從兩個位置到達：

• 從第(n-1)階爬1步：有 f(n-1) 種方法
• 從第(n-2)階爬2步：有 f(n-2) 種方法
• 總計：f(n-1) + f(n-2) 種方法

斐波那契數列對應關系

爬樓梯序列：1, 2, 3, 5, 8, 13, 21, 34, …
斐波那契序列：1, 1, 2, 3, 5, 8, 13, 21, …

關系：climbStairs(n) = fibonacci(n+1)

通項公式推導

斐波那契數列通項公式：

F(n) = (φ^n - ψ^n) / √5

其中：

• φ = (1 + √5) / 2 ≈ 1.618（黃金比例）
• ψ = (1 - √5) / 2 ≈ -0.618

因此：

climbStairs(n) = F(n+1) = (φ^(n+1) - ψ^(n+1)) / √5

執行流程圖

graph TDA[開始: 輸入n] --> B{邊界判斷}B -->|n ≤ 2| C[返回n]B -->|n > 2| D[選擇算法]D --> E[標準DP]D --> F[空間優化DP]D --> G[記憶化遞歸]D --> H[數學公式]D --> I[矩陣快速冪]E --> J[創建dp數組]F --> K[使用兩個變量]G --> L[遞歸+緩存]H --> M[黃金比例公式]I --> N[矩陣乘法]J --> O[循環計算f1-fn]K --> P[循環更新prev1,prev2]L --> Q[遞歸計算子問題]M --> R[直接計算結果]N --> S[快速冪計算]O --> T[返回dp[n]]P --> TQ --> TR --> TS --> TC --> U[結束]T --> U

實際應用

1. 組合計數：計算特定約束下的方案數
2. 路徑規劃：網格中的路徑計數問題
3. 動態規劃優化：狀態壓縮的經典例子
4. 算法面試：考察DP基礎的經典題目

擴展變形

1. 步數擴展：如果可以爬1、2、3步怎么辦？
2. 限制條件：某些臺階不能踩怎么處理？
3. 成本問題：每步有不同成本，求最小成本
4. 二維擴展：在網格中從左上到右下的路徑數

測試用例設計

// 基礎測試
n=1 → 1
n=2 → 2
n=3 → 3
n=4 → 5
n=5 → 8// 邊界測試
n=1 → 1 (最小值)
n=45 → 1836311903 (題目限制最大值)// 斐波那契驗證
n=10 → 89
n=20 → 10946
n=30 → 1346269// 性能測試
大數值測試各算法效率對比

數學性質

黃金比例的美

斐波那契數列中相鄰兩項的比值趨近于黃金比例φ：

lim(n→∞) F(n+1)/F(n) = φ = (1+√5)/2 ≈ 1.618

奇偶性質

F(n) 為偶數 ? n ≡ 0 (mod 3)

整除性質

gcd(F(m), F(n)) = F(gcd(m, n))

平方和性質

F(1)2 + F(2)2 + ... + F(n)2 = F(n) × F(n+1)

完整題解代碼

package mainimport ("fmt""math""time"
)// 方法1：動態規劃（標準解法）
func climbStairs(n int) int {if n <= 2 {return n}dp := make([]int, n+1)dp[1] = 1dp[2] = 2for i := 3; i <= n; i++ {dp[i] = dp[i-1] + dp[i-2]}return dp[n]
}// 方法2：空間優化動態規劃（最優解）
func climbStairsOptimized(n int) int {if n <= 2 {return n}prev2 := 1 // f(1)prev1 := 2 // f(2)for i := 3; i <= n; i++ {curr := prev1 + prev2prev2 = prev1prev1 = curr}return prev1
}// 方法3：遞歸 + 記憶化
func climbStairsMemo(n int) int {memo := make(map[int]int)return climbStairsMemoHelper(n, memo)
}func climbStairsMemoHelper(n int, memo map[int]int) int {if n <= 2 {return n}if val, exists := memo[n]; exists {return val}result := climbStairsMemoHelper(n-1, memo) + climbStairsMemoHelper(n-2, memo)memo[n] = resultreturn result
}// 方法4：數學公式（斐波那契通項公式）
func climbStairsFormula(n int) int {if n <= 2 {return n}sqrt5 := math.Sqrt(5)phi := (1 + sqrt5) / 2 // 黃金比例psi := (1 - sqrt5) / 2 // 共軛黃金比例// 斐波那契通項公式：F(n) = (φ^n - ψ^n) / √5// 這里是 F(n+1)，因為我們的序列是 f(1)=1, f(2)=2result := (math.Pow(phi, float64(n+1)) - math.Pow(psi, float64(n+1))) / sqrt5return int(math.Round(result))
}// 方法5：矩陣快速冪
func climbStairsMatrix(n int) int {if n <= 2 {return n}// 標準斐波那契矩陣：[[1,1],[1,0]]// F(n) = [[1,1],[1,0]]^(n-1) 的第一行第一列// 爬樓梯問題：climbStairs(n) = F(n+1)base := [][]int{{1, 1}, {1, 0}}result := matrixPower(base, n)// result[0][0] = F(n+1), result[0][1] = F(n)return result[0][0]
}func matrixPower(matrix [][]int, n int) [][]int {size := len(matrix)result := make([][]int, size)for i := range result {result[i] = make([]int, size)result[i][i] = 1 // 單位矩陣}base := make([][]int, size)for i := range base {base[i] = make([]int, size)copy(base[i], matrix[i])}for n > 0 {if n&1 == 1 {result = matrixMultiply(result, base)}base = matrixMultiply(base, base)n >>= 1}return result
}func matrixMultiply(a, b [][]int) [][]int {size := len(a)result := make([][]int, size)for i := range result {result[i] = make([]int, size)for j := 0; j < size; j++ {for k := 0; k < size; k++ {result[i][j] += a[i][k] * b[k][j]}}}return result
}// 測試函數
func testClimbingStairs() {fmt.Println("=== 70. 爬樓梯測試 ===")testCases := []struct {name     stringn        intexpected int}{// 基礎測試用例{"示例1", 2, 2},{"示例2", 3, 3},{"示例3", 4, 5},{"示例4", 5, 8},// 邊界測試用例{"最小值", 1, 1},{"小值測試", 6, 13},// 斐波那契驗證{"斐波那契-10", 10, 89},{"斐波那契-15", 15, 987},{"斐波那契-20", 20, 10946},// 中等規模測試{"中等規模-25", 25, 121393},{"中等規模-30", 30, 1346269},// 大規模測試（接近題目限制）{"大規模-40", 40, 165580141},{"最大值-45", 45, 1836311903},}methods := []struct {name stringfn   func(int) int}{{"標準DP", climbStairs},{"空間優化DP", climbStairsOptimized},{"記憶化遞歸", climbStairsMemo},{"數學公式", climbStairsFormula},{"矩陣快速冪", climbStairsMatrix},}for _, tc := range testCases {fmt.Printf("\n測試用例: %s (n=%d)\n", tc.name, tc.n)fmt.Printf("期望輸出: %d\n", tc.expected)for _, method := range methods {start := time.Now()result := method.fn(tc.n)duration := time.Since(start)status := "?"if result != tc.expected {status = "?"}fmt.Printf("%s %s: %d (耗時: %v)\n",status, method.name, result, duration)}}
}// 性能測試
func performanceTest() {fmt.Println("\n=== 性能測試 ===")testSizes := []int{10, 20, 30, 40, 45}methods := []struct {name stringfn   func(int) int}{{"標準DP", climbStairs},{"空間優化DP", climbStairsOptimized},{"記憶化遞歸", climbStairsMemo},{"數學公式", climbStairsFormula},{"矩陣快速冪", climbStairsMatrix},}for _, size := range testSizes {fmt.Printf("\n測試規模 n=%d:\n", size)for _, method := range methods {start := time.Now()result := method.fn(size)duration := time.Since(start)fmt.Printf("%s: 結果=%d, 耗時=%v\n",method.name, result, duration)}}
}// 算法分析
func algorithmAnalysis() {fmt.Println("\n=== 算法分析 ===")fmt.Println("時間復雜度:")fmt.Println("  ? 標準DP: O(n)")fmt.Println("  ? 空間優化DP: O(n)")fmt.Println("  ? 記憶化遞歸: O(n)")fmt.Println("  ? 數學公式: O(1) ? 最快")fmt.Println("  ? 矩陣快速冪: O(log n)")fmt.Println("\n空間復雜度:")fmt.Println("  ? 標準DP: O(n)")fmt.Println("  ? 空間優化DP: O(1) ? 最優實用")fmt.Println("  ? 記憶化遞歸: O(n)")fmt.Println("  ? 數學公式: O(1)")fmt.Println("  ? 矩陣快速冪: O(1)")fmt.Println("\n核心思想:")fmt.Println("  1. 斐波那契數列本質：f(n) = f(n-1) + f(n-2)")fmt.Println("  2. 狀態轉移：到達第n階只能從n-1或n-2階到達")fmt.Println("  3. 空間優化：只需要保存前兩個狀態")fmt.Println("  4. 數學加速：利用黃金比例直接計算")fmt.Println("\n推薦使用:")fmt.Println("  ? 面試/教學: 空間優化DP（平衡了效率和理解難度）")fmt.Println("  ? 高性能場景: 數學公式（需要注意浮點精度）")fmt.Println("  ? 大數場景: 矩陣快速冪（避免精度問題）")
}// 斐波那契數列分析
func fibonacciAnalysis() {fmt.Println("\n=== 斐波那契數列分析 ===")fmt.Println("爬樓梯與斐波那契的關系:")fmt.Printf("%-10s %-15s %-15s\n", "n", "climbStairs(n)", "fibonacci(n+1)")fmt.Println(repeatString("-", 45))for i := 1; i <= 10; i++ {climb := climbStairsOptimized(i)fib := fibonacci(i + 1)fmt.Printf("%-10d %-15d %-15d\n", i, climb, fib)}fmt.Println("\n黃金比例驗證:")for i := 5; i <= 15; i++ {fn := float64(climbStairsOptimized(i))fn1 := float64(climbStairsOptimized(i + 1))ratio := fn1 / fnphi := (1 + math.Sqrt(5)) / 2fmt.Printf("F(%d)/F(%d) = %.10f, φ = %.10f, 差值 = %.2e\n",i+1, i, ratio, phi, math.Abs(ratio-phi))}
}// 輔助函數：計算斐波那契數列
func fibonacci(n int) int {if n <= 2 {return 1}a, b := 1, 1for i := 3; i <= n; i++ {a, b = b, a+b}return b
}// 可視化演示
func visualDemo() {fmt.Println("\n=== 可視化演示 ===")n := 5fmt.Printf("示例: n = %d\n", n)fmt.Println("\n樓梯示意圖:")for i := n; i >= 1; i-- {spaces := repeatString(" ", (n-i)*2)fmt.Printf("%s[%d]\n", spaces, i)}fmt.Println(repeatString(" ", n*2) + "[0] 起點")fmt.Println("\n狀態轉移過程:")fmt.Println("f(1) = 1 (一種方法: 爬1步)")fmt.Println("f(2) = 2 (兩種方法: 1+1 或 2)")for i := 3; i <= n; i++ {prev1 := climbStairsOptimized(i - 1)prev2 := climbStairsOptimized(i - 2)curr := prev1 + prev2fmt.Printf("f(%d) = f(%d) + f(%d) = %d + %d = %d\n",i, i-1, i-2, prev1, prev2, curr)}fmt.Printf("\n最終答案: %d種方法\n", climbStairsOptimized(n))
}// 輔助函數：重復字符串
func repeatString(s string, count int) string {if count <= 0 {return ""}result := ""for i := 0; i < count; i++ {result += s}return result
}func main() {// 執行所有測試testClimbingStairs()performanceTest()algorithmAnalysis()fibonacciAnalysis()visualDemo()
}