經典動態規劃問題#

本節整理面試中最常見的經典 DP 問題，包括爬樓梯、零錢兌換、編輯距離和路徑規劃。這些問題是動態規劃的基石，掌握它們對於應對面試至關重要。

爬樓梯 ↗#

問題描述#

假設你要爬一個有 n 階的樓梯，每次可以爬 1 階或 2 階，問有多少種不同的方法可以爬到頂端？

n = 3 時，有 3 種方法：
1. 1步 + 1步 + 1步
2. 1步 + 2步
3. 2步 + 1步

解題思路#

從終點往回推導：到達第 n 階，只有兩種可能：

  • 從第 n-1 階走 1 步上來
  • 從第 n-2 階走 2 步上來

核心公式（斐波那契數列） > $$f(n) = f(n-1) + f(n-2)$$

邊界條件：$f(1) = 1$, $f(2) = 2$

程式碼實作#

爬樓梯的三種實作方式

遞迴 + 備忘錄（自頂向下）

fun climbStairs(n: Int, memo: IntArray): Int {
    if (n <= 2) return n
    if (memo[n] != 0) return memo[n]
    memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo)
    return memo[n]
}

動態規劃（自底向上）

fun climbStairs(n: Int): Int {
    if (n <= 2) return n
    val dp = IntArray(n + 1)
    dp[1] = 1
    dp[2] = 2
    for (i in 3..n) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

空間最佳化（O(1)）

fun climbStairs(n: Int): Int {
    if (n <= 2) return n
    var prev2 = 1
    var prev1 = 2
    for (i in 3..n) {
        val curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    }
    return prev1
}

進階思考 斐波那契數列存在 O(log N) 的解法——矩陣快速冪。 雖然面試不強制要求，但值得了解。

零錢兌換 ↗#

問題描述#

給定不同面值的硬幣和一個總金額，計算湊成該金額所需的最少硬幣數量。如果無法湊成，返回 -1。

輸入：coins = [1, 2, 5], amount = 11
輸出：3
解釋：11 = 5 + 5 + 1

解題思路#

問題轉化 這道題可以類比為「爬樓梯問題」：

  • 從地面（0）走到第 11 階
  • 每次可以走的步數 = 硬幣面值
  • 求最少走幾步到達目標

為什麼貪心法不適用？#

貪心法的陷阱 假設 coins = [1, 6, 7]，amount = 30

  • 貪心法：4×7 + 2×1 = 30，需要 6 枚硬幣
  • 最優解：5×6 = 30，只需 5 枚硬幣

優先使用最大面值不一定得到最少硬幣數！

狀態轉移方程#

狀態定義：dp[i] 表示湊成金額 i 所需的最少硬幣數

$$dp[i] = \min(dp[i - coin]) + 1, \quad coin \in coins$$

初始化技巧：

  • dp[0] = 0（金額 0 需要 0 枚硬幣）
  • 其他位置初始化為 amount + 1（相當於無窮大）
零錢兌換
fun coinChange(coins: IntArray, amount: Int): Int {
    // 初始化為「無窮大」（amount+1 已不可能達成）
    val dp = IntArray(amount + 1) { amount + 1 }
    dp[0] = 0

    for (i in 1..amount) {
        for (coin in coins) {
            if (coin <= i) {
                dp[i] = minOf(dp[i], dp[i - coin] + 1)
            }
        }
    }

    // 若 dp[amount] 未被更新，表示無解
    return if (dp[amount] > amount) -1 else dp[amount]
}

複雜度分析：

  • 時間複雜度：O(amount × n)
  • 空間複雜度：O(amount)

編輯距離 ↗#

問題描述#

給定兩個單詞 word1 和 word2，計算將 word1 轉換成 word2 所需的最少操作數。

允許的操作：

  1. 插入一個字元
  2. 刪除一個字元
  3. 替換一個字元
輸入：word1 = "horse", word2 = "ros"
輸出：3
解釋：horse → rorse（替換）→ rose（刪除）→ ros（刪除）

為什麼這道題很重要？ 編輯距離是字串匹配問題的經典案例，也是 DP 的必修題。 如果對字串 DP 不夠熟練，請務必反覆練習這道題。

狀態定義#

dp[i][j] 表示 word1 的前 i 個字元轉換成 word2 的前 j 個字元所需的最少操作數。

狀態轉移方程#

字元相等時（word1[i-1] == word2[j-1]） $$dp[i][j] = dp[i-1][j-1]$$

字元不等時 $$dp[i][j] = 1 + \min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])$$

其中：

  • dp[i-1][j-1] + 1：替換操作
  • dp[i-1][j] + 1：刪除 word1[i-1]
  • dp[i][j-1] + 1：插入（等同於 word2 減少一個字元）

初始化#

dp[0][0] = 0    （空字串轉空字串）
dp[i][0] = i    （刪除 i 次）
dp[0][j] = j    （插入 j 次）
編輯距離
fun minDistance(word1: String, word2: String): Int {
    val m = word1.length
    val n = word2.length
    val dp = Array(m + 1) { IntArray(n + 1) }

    // 初始化
    for (i in 0..m) dp[i][0] = i
    for (j in 0..n) dp[0][j] = j

    // 填充 DP 表
    for (i in 1..m) {
        for (j in 1..n) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]
            } else {
                dp[i][j] = 1 + minOf(
                    dp[i - 1][j - 1],  // 替換
                    dp[i - 1][j],      // 刪除
                    dp[i][j - 1],      // 插入
                )
            }
        }
    }

    return dp[m][n]
}

變體：加權操作 如果不同操作有不同的權重，只需將 +1 改為對應的權重： min(dp[i][j-1]+插入權重, dp[i-1][j]+刪除權重, dp[i-1][j-1]+替換權重)

路徑規劃問題#

基礎版：不同路徑 ↗#

問題：機器人位於 m×n 網格的左上角，每次只能向下或向右移動一步。問到達右下角有多少條不同路徑？

狀態轉移方程：

$$ DP[i][j] = \begin{cases} 1, & i = 0 \text{ 或 } j = 0 \ DP[i-1][j] + DP[i][j-1], & \text{其他} \end{cases} $$

不同路徑
fun uniquePaths(m: Int, n: Int): Int {
    val dp = Array(m) { IntArray(n) }

    // 初始化：第一行和第一列都是 1
    for (i in 0 until m) dp[i][0] = 1
    for (j in 0 until n) dp[0][j] = 1

    for (i in 1 until m) {
        for (j in 1 until n) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        }
    }

    return dp[m - 1][n - 1]
}

進階版：帶障礙物的路徑#

問題：網格中有障礙物（標記為 1），求從左上到右下的路徑數。

關鍵修改：有障礙的格子路徑數為 0

$$ DP[i][j] = \begin{cases} 0, & grid[i][j] = 1 \text{ (障礙物)} \ DP[i-1][j] + DP[i][j-1], & \text{其他} \end{cases} $$

跳躍遊戲 ↗#

問題：陣列中每個元素表示可跳躍的最大長度，判斷能否到達最後一個位置。

輸入：[2, 3, 1, 1, 4]
輸出：true（可以到達）

輸入：[3, 2, 1, 0, 4]
輸出：false（無法跳過 0）

狀態定義：dp[i] 表示能否到達位置 i

狀態轉移：

$$ dp[i] = \begin{cases} True, & i = 0 \ True, & \exists j < i, dp[j] = true \text{ 且 } j + nums[j] \geq i \ False, & \text{其他} \end{cases} $$

跳躍遊戲
fun canJump(nums: IntArray): Boolean {
    val n = nums.size
    if (n <= 1) return true

    val dp = BooleanArray(n)
    dp[0] = true

    for (i in 1 until n) {
        for (j in 0 until i) {
            if (dp[j] && j + nums[j] >= i) {
                dp[i] = true
                break
            }
        }
    }

    return dp[n - 1]
}

問題類型總結#

問題類型狀態定義時間複雜度
爬樓梯求方案數dp[i] = 到達 i 的方法數O(n)
零錢兌換求最優解dp[i] = 湊成 i 的最少硬幣數O(amount × n)
編輯距離求最優解dp[i][j] = 轉換的最少操作數O(m × n)
路徑規劃求方案數dp[i][j] = 到達 (i,j) 的路徑數O(m × n)
跳躍遊戲求可行性dp[i] = 能否到達位置 iO(n²)

學習建議 這些經典問題是動態規劃的基石。建議：

  1. 先理解狀態定義和轉移方程
  2. 手動模擬填表過程
  3. 嘗試空間最佳化
  4. 舉一反三，解決變體問題
Backward 子陣列與子序列 股票交易系列 Forward