經典動態規劃問題#

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

爬樓梯 (Climbing Stairs)#

問題描述#

假設你要爬一個有 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$

程式碼實現#

爬樓梯的三種實現方式

方式一：遞迴 + 備忘錄（自頂向下）

int climbStairs(int n, int[] memo) {
    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];
}

方式二：動態規劃（自底向上）

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

方式三：空間優化（O(1)）

int climbStairs(int n) {
    if (n <= 2) return n;
    int prev2 = 1, prev1 = 2;
    for (int i = 3; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

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

零錢兌換 (Coin Change)#

問題描述#

給定不同面值的硬幣和一個總金額，計算湊成該金額所需的最少硬幣數量。如果無法湊成，返回 -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（相當於無窮大）
零錢兌換 Java 實現
int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    // 初始化為「無窮大」
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    // 若 dp[amount] 未被更新，表示無解
    return dp[amount] > amount ? -1 : dp[amount];
}

複雜度分析：

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

編輯距離 (Edit Distance)#

問題描述#

給定兩個單詞 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 個字元所需的最少操作數。

狀態轉移方程#

情況 A：字元相等（word1[i-1] == word2[j-1]） $$dp[i][j] = dp[i-1][j-1]$$

情況 B：字元不等 $$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 次）
編輯距離 Java 實現
int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];

    // 初始化
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;

    // 填充 DP 表
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(
                    dp[i - 1][j - 1],  // 替換
                    Math.min(
                        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} $$

不同路徑 Java 實現
int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];

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

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            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} $$

跳躍遊戲 (Jump Game)#

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

輸入：[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} $$

跳躍遊戲 Java 實現
boolean canJump(int[] nums) {
    int n = nums.length;
    if (n <= 1) return true;

    boolean[] dp = new boolean[n];
    dp[0] = true;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            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^2)

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

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