面試白板題：動態規劃與排序

什麼是動態規劃？

💡 比喻：聰明的備忘錄 假設你在爬樓梯，每次可以爬 1 或 2 階。 如果有人問你「爬到第 10 階有幾種方法？」—— 你可以把「爬到第 1 階」「爬到第 2 階」的答案記下來， 後面的答案就是前面兩個相加，不用重複計算。 這就是動態規劃的核心：記住已經算過的結果。

題目一：Climbing Stairs（爬樓梯）

暴力遞迴 O(2^n) — 超時！

// 暴力遞迴：每次選擇爬 1 或 2 階 // Brute force: exponential time
public int ClimbStairsBrute(int n) // 爬樓梯暴力解
{
    if (n <= 2) return n; // 1 階有 1 種，2 階有 2 種
    return ClimbStairsBrute(n - 1) + ClimbStairsBrute(n - 2); // 遞迴計算
    // ❌ 會重複計算非常多次，指數級時間複雜度 // 會超時！
}

記憶化遞迴 O(n)

// 記憶化遞迴：用字典記住算過的結果 // Memoization: cache computed results
public int ClimbStairsMemo(int n, Dictionary<int, int>? memo = null) // 記憶化版本
{
    memo ??= new Dictionary<int, int>(); // 初始化備忘錄
    if (n <= 2) return n; // 基本情況
    if (memo.ContainsKey(n)) return memo[n]; // 如果算過了直接回傳
    memo[n] = ClimbStairsMemo(n - 1, memo) + ClimbStairsMemo(n - 2, memo); // 計算並記住
    return memo[n]; // 回傳結果
}

DP 表格解法 O(n)

// DP 表格：從小問題往上計算 // Bottom-up DP table
public int ClimbStairsDP(int n) // 爬樓梯 DP 解法
{
    if (n <= 2) return n; // 基本情況
    int[] dp = new int[n + 1]; // 建立 DP 表格
    dp[1] = 1; // 1 階有 1 種方法
    dp[2] = 2; // 2 階有 2 種方法
    for (int i = 3; i <= n; i++) // 從第 3 階開始算
    {
        dp[i] = dp[i - 1] + dp[i - 2]; // 等於前兩階的方法數相加
    }
    return dp[n]; // 回傳第 n 階的方法數
}

空間優化 O(1)

// 空間優化：只需要前兩個數字 // Space optimized: only need two variables
public int ClimbStairsOptimal(int n) // 最佳化爬樓梯
{
    if (n <= 2) return n; // 基本情況
    int prev2 = 1; // 前兩階的方法數
    int prev1 = 2; // 前一階的方法數
    for (int i = 3; i <= n; i++) // 從第 3 階開始
    {
        int current = prev1 + prev2; // 當前階 = 前一階 + 前兩階
        prev2 = prev1; // 更新前兩階
        prev1 = current; // 更新前一階
    }
    return prev1; // 回傳結果
}

題目二：Coin Change（零錢問題）

題目說明

給定不同面額的硬幣和一個總金額，計算湊出總金額所需的最少硬幣數。

暴力遞迴

// 暴力遞迴：嘗試每種硬幣 // Brute force: try every coin
public int CoinChangeBrute(int[] coins, int amount) // 零錢問題暴力解
{
    if (amount == 0) return 0; // 金額為 0 不需要硬幣
    if (amount < 0) return -1; // 金額為負代表這條路不通
    int minCoins = int.MaxValue; // 初始化最小硬幣數
    foreach (int coin in coins) // 嘗試每種硬幣
    {
        int result = CoinChangeBrute(coins, amount - coin); // 遞迴計算剩餘金額
        if (result >= 0 && result + 1 < minCoins) // 如果這條路可行且更少
        {
            minCoins = result + 1; // 更新最小硬幣數
        }
    }
    return minCoins == int.MaxValue ? -1 : minCoins; // 回傳結果
}

DP 表格解法

// DP 解法：建表從金額 0 算到目標金額 // DP: build table from 0 to amount
public int CoinChangeDP(int[] coins, int amount) // 零錢問題 DP 解法
{
    int[] dp = new int[amount + 1]; // 建立 DP 表格
    Array.Fill(dp, amount + 1); // 初始化為不可能的大數
    dp[0] = 0; // 金額 0 需要 0 個硬幣
    for (int i = 1; i <= amount; i++) // 從金額 1 算到目標金額
    {
        foreach (int coin in coins) // 嘗試每種硬幣
        {
            if (coin <= i) // 如果這個硬幣面額不超過當前金額
            {
                dp[i] = Math.Min(dp[i], dp[i - coin] + 1); // 取較少的硬幣數
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount]; // 回傳結果
}

DP 推導過程圖解

硬幣 = [1, 3, 5]，目標金額 = 7

dp[0] = 0  （0 元需要 0 個硬幣）
dp[1] = 1  （1 元 → 用 1 個「1 元」）
dp[2] = 2  （2 元 → 用 2 個「1 元」）
dp[3] = 1  （3 元 → 用 1 個「3 元」）
dp[4] = 2  （4 元 → 用 1+3）
dp[5] = 1  （5 元 → 用 1 個「5 元」）
dp[6] = 2  （6 元 → 用 1+5 或 3+3）
dp[7] = 3  （7 元 → 用 1+1+5 或 1+3+3）

答案：dp[7] = 3

題目三：Quick Sort vs Merge Sort 實作

Quick Sort（快速排序）

// 快速排序：選基準值，分成大小兩堆 // Quick Sort: pivot partitioning
public void QuickSort(int[] arr, int low, int high) // 快速排序主方法
{
    if (low < high) // 還有元素要排
    {
        int pivotIndex = Partition(arr, low, high); // 取得基準值的正確位置
        QuickSort(arr, low, pivotIndex - 1); // 遞迴排左半邊
        QuickSort(arr, pivotIndex + 1, high); // 遞迴排右半邊
    }
}

private int Partition(int[] arr, int low, int high) // 分割：把小的放左邊大的放右邊
{
    int pivot = arr[high]; // 選最後一個元素作為基準值
    int i = low - 1; // i 指向小於基準值區域的邊界
    for (int j = low; j < high; j++) // 走訪所有元素
    {
        if (arr[j] < pivot) // 如果當前元素小於基準值
        {
            i++; // 擴大小於區域
            (arr[i], arr[j]) = (arr[j], arr[i]); // 交換位置
        }
    }
    (arr[i + 1], arr[high]) = (arr[high], arr[i + 1]); // 基準值放到正確位置
    return i + 1; // 回傳基準值的索引
}

Merge Sort（合併排序）

// 合併排序：分成兩半再合併 // Merge Sort: divide and merge
public int[] MergeSort(int[] arr) // 合併排序主方法
{
    if (arr.Length <= 1) return arr; // 只有一個元素不用排
    int mid = arr.Length / 2; // 找到中間點
    int[] left = MergeSort(arr[..mid]); // 遞迴排左半邊
    int[] right = MergeSort(arr[mid..]); // 遞迴排右半邊
    return Merge(left, right); // 合併兩個已排序的陣列
}

private int[] Merge(int[] left, int[] right) // 合併兩個已排序陣列
{
    int[] result = new int[left.Length + right.Length]; // 建立結果陣列
    int i = 0, j = 0, k = 0; // 三個索引指標
    while (i < left.Length && j < right.Length) // 當兩邊都還有元素
    {
        if (left[i] <= right[j]) // 左邊的比較小
            result[k++] = left[i++]; // 放入左邊的元素
        else // 右邊的比較小
            result[k++] = right[j++]; // 放入右邊的元素
    }
    while (i < left.Length) result[k++] = left[i++]; // 放入左邊剩餘的元素
    while (j < right.Length) result[k++] = right[j++]; // 放入右邊剩餘的元素
    return result; // 回傳合併後的陣列
}

比較表

特性            Quick Sort          Merge Sort
──────────────────────────────────────────────
平均時間        O(n log n)          O(n log n)
最差時間        O(n²)               O(n log n)
空間複雜度      O(log n)            O(n)
穩定排序        ❌ 不穩定            ✅ 穩定
原地排序        ✅ 是                ❌ 否
適合場景        一般排序              需要穩定排序時

題目四：Binary Search 變體

基本二分搜尋

// 基本二分搜尋：在已排序陣列中找目標值 // Basic binary search
public int BinarySearch(int[] nums, int target) // 二分搜尋
{
    int left = 0; // 左邊界
    int right = nums.Length - 1; // 右邊界
    while (left <= right) // 當搜尋範圍還有效
    {
        int mid = left + (right - left) / 2; // 計算中間位置（避免溢位）
        if (nums[mid] == target) return mid; // 找到了
        if (nums[mid] < target) left = mid + 1; // 目標在右半邊
        else right = mid - 1; // 目標在左半邊
    }
    return -1; // 找不到回傳 -1
}

變體一：找第一個出現的位置

// 變體：找目標值第一次出現的位置 // Variant: find first occurrence
public int FindFirst(int[] nums, int target) // 找第一個出現的位置
{
    int left = 0; // 左邊界
    int right = nums.Length - 1; // 右邊界
    int result = -1; // 預設找不到
    while (left <= right) // 當搜尋範圍還有效
    {
        int mid = left + (right - left) / 2; // 計算中間位置
        if (nums[mid] == target) // 找到目標值
        {
            result = mid; // 記錄位置
            right = mid - 1; // 繼續往左找更早出現的
        }
        else if (nums[mid] < target) left = mid + 1; // 目標在右半邊
        else right = mid - 1; // 目標在左半邊
    }
    return result; // 回傳第一次出現的位置
}

變體二：找插入位置

// 變體：找目標值應該插入的位置 // Variant: find insert position
public int SearchInsertPosition(int[] nums, int target) // 找插入位置
{
    int left = 0; // 左邊界
    int right = nums.Length - 1; // 右邊界
    while (left <= right) // 當搜尋範圍還有效
    {
        int mid = left + (right - left) / 2; // 計算中間位置
        if (nums[mid] == target) return mid; // 找到直接回傳
        if (nums[mid] < target) left = mid + 1; // 目標在右半邊
        else right = mid - 1; // 目標在左半邊
    }
    return left; // left 就是應該插入的位置
}

🤔 我這樣寫為什麼會錯？

錯誤一：DP 忘記初始化

// ❌ 錯誤：dp 陣列沒有初始化 // Wrong: dp not initialized
int[] dp = new int[amount + 1]; // 預設都是 0
dp[0] = 0; // 設定起點
// ❌ dp[1] 到 dp[amount] 都是 0，Math.Min 永遠選 0

// ✅ 正確：初始化為不可能的大數 // Correct: initialize to impossible value
int[] dp2 = new int[amount + 1]; // 建立 DP 表格
Array.Fill(dp2, amount + 1); // 填入大數代表「還沒算」
dp2[0] = 0; // 金額 0 需要 0 個硬幣

錯誤二：二分搜尋中間值溢位

// ❌ 錯誤：可能溢位 // Wrong: potential overflow
int mid = (left + right) / 2; // ❌ left + right 可能超過 int.MaxValue

// ✅ 正確：避免溢位的寫法 // Correct: overflow-safe
int mid2 = left + (right - left) / 2; // 永遠不會溢位

錯誤三：Quick Sort 基準值選擇不當

// ❌ 風險：總是選第一個或最後一個元素 // Risky: always pick first/last
int pivot = arr[low]; // 如果陣列已排序，會退化成 O(n²)

// ✅ 更好：隨機選擇或三數取中 // Better: random or median-of-three
int randomIndex = new Random().Next(low, high + 1); // 隨機選一個
(arr[randomIndex], arr[high]) = (arr[high], arr[randomIndex]); // 交換到最後
int pivot2 = arr[high]; // 再用最後一個當基準值

DP 解題框架

解 DP 題目的五步驟：

1. 定義狀態：dp[i] 代表什麼？
   → 爬樓梯：dp[i] = 爬到第 i 階的方法數
   → 零錢：dp[i] = 湊出金額 i 的最少硬幣數

2. 定義轉移方程：dp[i] 怎麼從前面的值算出來？
   → 爬樓梯：dp[i] = dp[i-1] + dp[i-2]
   → 零錢：dp[i] = min(dp[i], dp[i-coin] + 1)

3. 初始化：dp[0] 或 dp[1] 的值是什麼？
   → 爬樓梯：dp[1] = 1, dp[2] = 2
   → 零錢：dp[0] = 0

4. 計算順序：從小到大填表格

5. 回傳結果：dp[n] 就是答案