Yoru Karu Studio
Yoru Karu Studio

LeetCode 解題思路：70 .Climbing Stairs（爬樓梯）

從遞迴到動態規劃，深入理解經典的爬樓梯問題

luk 收錄於 Leetcode
 約 1400 字 預計閱讀 7 分鐘 

LeetCode 解題思路：Climbing Stairs（爬樓梯）

題目描述

你正在爬樓梯。需要 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

核心概念

1. 問題本質分析

這是一個經典的動態規劃入門題。關鍵洞察：

到達第 n 階的方法數 = 到達第 (n-1) 階的方法數 + 到達第 (n-2) 階的方法數

為什麼？因為到達第 n 階只有兩種方式：

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

2. 視覺化理解 

n = 4 的所有路徑：

起點 → 1 → 2 → 3 → 4  (1+1+1+1)
起點 → 1 → 2 → 4      (1+1+2)
起點 → 1 → 3 → 4      (1+2+1)
起點 → 2 → 3 → 4      (2+1+1)
起點 → 2 → 4          (2+2)

總共 5 種方法

3. 遞推關係 

f(n) = 爬到第 n 階的方法數

基礎情況：
f(1) = 1  (只有一種方法：爬 1 階)
f(2) = 2  (兩種方法：1+1 或 2)

遞推關係：
f(n) = f(n-1) + f(n-2), n >= 3

這實際上就是費波那契數列！

解法一：遞迴（最直觀但效率低）

思路

直接根據遞推關係實現。

程式碼實現 

class Solution:
    def climbStairs(self, n: int) -> int:
        # 基礎情況
        if n <= 2:
            return n
        
        # 遞迴關係
        return self.climbStairs(n-1) + self.climbStairs(n-2)

為什麼效率低？ 

計算 climbStairs(5) 的過程：

                    f(5)
                   /    \
                f(4)      f(3)
               /    \    /    \
            f(3)    f(2) f(2) f(1)
           /    \
         f(2)   f(1)

發現問題了嗎？f(3) 被計算了 2 次，f(2) 被計算了 3 次！

時間複雜度：O(2^n) - 指數級增長！

解法二：記憶化遞迴（優化版遞迴）

思路

使用記憶化（Memoization）避免重複計算。

程式碼實現 

class Solution:
    def climbStairs(self, n: int) -> int:
        memo = {}
        
        def climb(n):
            # 檢查快取
            if n in memo:
                return memo[n]
            
            # 基礎情況
            if n <= 2:
                return n
            
            # 計算並儲存結果
            memo[n] = climb(n-1) + climb(n-2)
            return memo[n]
        
        return climb(n)

使用 @lru_cache 裝飾器（Python 特色） 

from functools import lru_cache

class Solution:
    def climbStairs(self, n: int) -> int:
        @lru_cache(None)
        def climb(n):
            if n <= 2:
                return n
            return climb(n-1) + climb(n-2)
        
        return climb(n)

時間複雜度：O(n) - 每個子問題只計算一次

解法三：動態規劃（推薦）

思路

從底向上計算，避免遞迴的函數呼叫開銷。

程式碼實現 

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        
        # dp[i] 表示爬到第 i 階的方法數
        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2
        
        # 從第 3 階開始計算
        for i in range(3, n + 1):
            dp[i] = dp[i-1] + dp[i-2]
        
        return dp[n]

執行過程詳解 

計算 n = 5：

初始：dp = [0, 1, 2, 0, 0, 0]
            ↑  ↑  ↑
           i=0 1  2

i = 3: dp[3] = dp[2] + dp[1] = 2 + 1 = 3
       dp = [0, 1, 2, 3, 0, 0]

i = 4: dp[4] = dp[3] + dp[2] = 3 + 2 = 5
       dp = [0, 1, 2, 3, 5, 0]

i = 5: dp[5] = dp[4] + dp[3] = 5 + 3 = 8
       dp = [0, 1, 2, 3, 5, 8]

返回 dp[5] = 8

解法四：空間優化的動態規劃（最優）

思路

觀察到我們只需要前兩個值，不需要整個陣列。

程式碼實現 

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        
        # 只需要記錄前兩個值
        prev2 = 1  # f(n-2)
        prev1 = 2  # f(n-1)
        
        for i in range(3, n + 1):
            current = prev1 + prev2
            prev2 = prev1
            prev1 = current
        
        return prev1

更優雅的寫法 

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        
        a, b = 1, 2
        for _ in range(3, n + 1):
            a, b = b, a + b
        
        return b

空間複雜度降至 O(1)！

解法五：矩陣快速冪（進階）

數學原理

費波那契數列可以用矩陣運算表示：

[f(n+1)]   [1 1]^n   [1]
[f(n)  ] = [1 0]   × [0]

程式碼實現 

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        
        def matrix_multiply(a, b):
            # 2x2 矩陣相乘
            return [
                [a[0][0]*b[0][0] + a[0][1]*b[1][0], a[0][0]*b[0][1] + a[0][1]*b[1][1]],
                [a[1][0]*b[0][0] + a[1][1]*b[1][0], a[1][0]*b[0][1] + a[1][1]*b[1][1]]
            ]
        
        def matrix_power(matrix, n):
            # 快速冪算法
            if n == 1:
                return matrix
            
            if n % 2 == 0:
                half = matrix_power(matrix, n // 2)
                return matrix_multiply(half, half)
            else:
                return matrix_multiply(matrix, matrix_power(matrix, n - 1))
        
        # 基礎矩陣
        base = [[1, 1], [1, 0]]
        result = matrix_power(base, n)
        
        return result[0][0]

時間複雜度：O(log n)

解法六：通項公式（數學方法）

數學推導

費波那契數列的通項公式（Binet’s Formula）：

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

其中：
φ = (1 + √5) / 2 ≈ 1.618 (黃金比例)
ψ = (1 - √5) / 2 ≈ -0.618

程式碼實現 

import math

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        
        # 注意：這題的費波那契數列從 f(1)=1, f(2)=2 開始
        # 所以實際上是標準費波那契數列向右移一位
        sqrt5 = math.sqrt(5)
        phi = (1 + sqrt5) / 2
        psi = (1 - sqrt5) / 2
        
        # 計算 f(n+1)
        return int((math.pow(phi, n+1) - math.pow(psi, n+1)) / sqrt5)

變化題型

1. 每次可以爬 1, 2, 或 3 階 

def climbStairs3(n: int) -> int:
    if n == 0:
        return 1
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    dp[2] = 2
    
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    
    return dp[n]

2. 每次可以爬 k 階內的任意階數 

def climbStairsK(n: int, k: int) -> int:
    dp = [0] * (n + 1)
    dp[0] = 1
    
    for i in range(1, n + 1):
        for j in range(1, min(k, i) + 1):
            dp[i] += dp[i - j]
    
    return dp[n]

3. 某些階梯不能踩（有障礙物） 

def climbStairsWithObstacles(n: int, obstacles: List[int]) -> int:
    if 1 in obstacles:
        return 0
    
    dp = [0] * (n + 1)
    dp[0] = 1
    
    for i in range(1, n + 1):
        if i in obstacles:
            dp[i] = 0
        else:
            if i >= 1:
                dp[i] += dp[i-1]
            if i >= 2:
                dp[i] += dp[i-2]
    
    return dp[n]

4. 計算最少步數 

def minClimbStairs(n: int) -> int:
    if n <= 2:
        return 1
    
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    dp[2] = 1
    
    for i in range(3, n + 1):
        dp[i] = min(dp[i-1], dp[i-2]) + 1
    
    return dp[n]

5. 計算爬樓梯的成本 

def minCostClimbingStairs(cost: List[int]) -> int:
    n = len(cost)
    dp = [0] * (n + 1)
    
    for i in range(2, n + 1):
        dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
    
    return dp[n]

常見錯誤與陷阱

錯誤 1：邊界條件處理不當 

# ❌ 錯誤！沒有處理 n = 1 的情況
def climbStairs(self, n: int) -> int:
    dp = [0] * n
    dp[0] = 1
    dp[1] = 2  # 當 n = 1 時，索引越界！
    # ...

正確做法：

# ✅ 正確處理邊界
def climbStairs(self, n: int) -> int:
    if n <= 2:
        return n
    # ...

錯誤 2：陣列大小錯誤 

# ❌ 錯誤！陣列大小不夠
def climbStairs(self, n: int) -> int:
    dp = [0] * n  # 應該是 n + 1
    # ...

錯誤 3：初始值設定錯誤 

# ❌ 錯誤！初始值錯誤
def climbStairs(self, n: int) -> int:
    dp = [0] * (n + 1)
    dp[0] = 0  # 應該是 dp[1] = 1
    dp[1] = 1  # 應該是 dp[2] = 2
    # ...

錯誤 4：遞迴沒有基礎情況 

# ❌ 錯誤！無限遞迴
def climbStairs(self, n: int) -> int:
    return self.climbStairs(n-1) + self.climbStairs(n-2)

複雜度分析

解法時間複雜度空間複雜度優點缺點
純遞迴O(2^n)O(n)直觀易懂效率極低
記憶化遞迴O(n)O(n)相對直觀遞迴開銷
動態規劃O(n)O(n)效率高需要額外空間
優化DPO(n)O(1)最優解程式碼較抽象
矩陣快速冪O(log n)O(1)極快實現複雜
數學公式O(1)O(1)最快浮點數精度問題

相關題目推薦

  1. LeetCode 509: Fibonacci Number - 標準費波那契數列
  2. LeetCode 746: Min Cost Climbing Stairs - 帶成本的爬樓梯
  3. LeetCode 1137: N-th Tribonacci Number - 三步爬樓梯
  4. LeetCode 198: House Robber - 類似的DP問題
  5. LeetCode 91: Decode Ways - 解碼方法（類似思路）
  6. LeetCode 62: Unique Paths - 路徑計數問題

實戰技巧總結

1. 動態規劃模板 

def dp_template(n):
    # 1. 定義狀態
    # dp[i] = ...的含義
    
    # 2. 初始化
    dp = [初始值] * (n + 1)
    dp[基礎情況] = 基礎值
    
    # 3. 狀態轉移
    for i in range(起始, n + 1):
        dp[i] = 根據之前的狀態計算
    
    # 4. 返回結果
    return dp[n]

2. 空間優化技巧

當 DP 只依賴前幾個狀態時：

# 原始版本
dp = [0] * (n + 1)
for i in range(n + 1):
    dp[i] = dp[i-1] + dp[i-2]

# 優化版本
prev2, prev1 = 初始值
for i in range(n):
    current = prev1 + prev2
    prev2, prev1 = prev1, current

3. 遞迴轉 DP 的步驟

  1. 寫出遞迴解法
  2. 找出重複子問題
  3. 定義 DP 狀態
  4. 寫出狀態轉移方程
  5. 確定初始值和計算順序
  6. 優化空間複雜度

4. 調試技巧 

def climbStairs(self, n: int) -> int:
    print(f"計算爬 {n} 階樓梯的方法數")
    
    if n <= 2:
        return n
    
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
        print(f"dp[{i}] = dp[{i-1}] + dp[{i-2}] = {dp[i-1]} + {dp[i-2]} = {dp[i]}")
    
    print(f"DP 陣列: {dp}")
    return dp[n]

進階思考題

1. 如果可以向下爬樓梯？ 

def climbStairsBidirectional(n: int) -> int:
    # 可以向上爬 1 或 2 階，也可以向下爬 1 階
    # 從 0 到 n，最後必須停在 n
    # 提示：使用二維 DP
    pass

2. 計算所有路徑？ 

def allClimbingPaths(n: int) -> List[List[int]]:
    # 返回所有可能的爬樓梯路徑
    # 例如 n = 3: [[1,1,1], [1,2], [2,1]]
    pass

3. 概率版本？ 

def climbStairsProbability(n: int, p: float) -> float:
    # 每次有 p 的概率爬 1 階，(1-p) 的概率爬 2 階
    # 計算成功爬到第 n 階的概率
    pass

總結

爬樓梯問題是動態規劃的經典入門題，透過這題可以學到：

  1. 遞迴思維：將大問題分解為小問題
  2. 記憶化：避免重複計算
  3. 動態規劃：自底向上構建解答
  4. 空間優化：滾動陣列技巧
  5. 數學思維：發現問題背後的數學模型

關鍵要點：

  • 識別費波那契數列模式
  • 理解狀態轉移方程
  • 注意邊界條件處理
  • 學會空間優化技巧
  • 舉一反三解決變化題型

練習建議

  1. 基礎練習：

    • 手動模擬小規模輸入
    • 實現所有解法並比較
    • 畫出遞迴樹理解重複計算

  2. 進階練習：

    • 嘗試不同的狀態定義
    • 實現各種變化題型
    • 優化程式碼效能

  3. 理論學習：

    • 研究費波那契數列性質
    • 學習矩陣快速冪算法
    • 理解動態規劃的本質

  4. 實際應用：

    • 路徑規劃問題
    • 組合計數問題
    • 概率計算問題

記住：動態規劃的核心是找到最優子結構和重疊子問題！

更新於 2024-12-30 
CC BY-NC-SA 4.0
閱讀原始文檔
LeetcodeAlgorithmDynamic-ProgrammingRecursion
返回 | 主頁
0%