動態規劃入門：從貪心演算法說起#

為什麼從貪心開始？#

動態規劃的本質是求解最優化問題。在學習 DP 之前，我們需要先理解兩個重要概念：

  • 局部最優解：在一定範圍或條件下的最優決策
  • 整體最優解：所有解決方案中的最優決策

核心觀點 整體最優解一定是一個局部最優解，但局部最優解不一定是整體最優解。 貪心演算法是求解局部最優的經典方法，而動態規劃則是為了求解整體最優。

硬幣找零問題#

問題描述#

給定 n 種不同面值的硬幣 c[0], c[1], ... c[n]，以及總金額 k。編寫函式計算出最少需要幾枚硬幣凑出這個金額。如果無法凑出，返回 -1。

範例：

輸入：c[0]=1, c[1]=2, c[2]=5, k=12
輸出：3
解釋：12 = 5 + 5 + 2

貪心演算法的嘗試#

最直觀的想法：優先使用面值最大的硬幣。

c[0]=5, c[1]=3, k=11
貪心思路：先放 5 (餘6) → 再放 5 (餘1) → 無法繼續！

貪心演算法的局限性 純粹的貪心只考慮當前的最大利益，既不向前多看一步，也不向後多看一步。 這種「過於貪心」會導致我們進入死胡同。

加入回溯的改進#

當貪心失效時，我們需要「退一步」：把第 2 步放入的 5 元硬幣取出，改放 3 元硬幣。

改進後：5 + 3 + 3 = 11 ✓
貪心 + 回溯的程式碼
int getMinCoinCountOfValue(int total, int[] values, int valueIndex) {
    if (valueIndex == values.length) { return Integer.MAX_VALUE; }

    int minResult = Integer.MAX_VALUE;
    int currentValue = values[valueIndex];
    int maxCount = total / currentValue;

    for (int count = maxCount; count >= 0; count--) {
        int rest = total - count * currentValue;

        if (rest == 0) {
            minResult = Math.min(minResult, count);
            break;
        }

        int restCount = getMinCoinCountOfValue(rest, values, valueIndex + 1);
        if (restCount == Integer.MAX_VALUE) {
            if (count == 0) { break; }
            continue;
        }

        minResult = Math.min(minResult, count + restCount);
    }
    return minResult;
}

最優化問題的本質#

從數學角度理解硬幣找零：

設 5 元硬幣數量為 x₀，3 元硬幣數量為 x₁，目標金額為 y。

  • 目標函式：f(x₀, x₁) = x₀ + x₁（求最小值）
  • 約束條件：5x₀ + 3x₁ = y

用數學表示： $$\arg\min_{(x_0,x_1) \in S}(x_0 + x_1)$$

關鍵洞察 離散型最優化問題的本質：從所有滿足條件的組合中找出使目標函式最小的那個組合。 這就是為什麼「穷举」是求最值問題的核心——我們需要找到所有可能的答案。

貪心演算法總結#

貪心的基本思路#

  1. 根據問題建立數學模型
  2. 把問題劃分成若干子問題
  3. 對每個子問題求解局部最優
  4. 合併得到基於局部最優的解

貪心的局限性#

  1. 不能保證最佳解：可能錯過整體最優
  2. 不能求最大或最小問題：只能在約束條件下找可行解
  3. 只適用於特定問題：需要問題具有貪心選擇性質

重要結論 所有貪心的思路都是最優化求解的根本思想。回溯解決的是正確性問題，而動態規劃則是解決時間複雜度的問題。

貪心演算法是求解整體最優的真正思路源頭，這就是為什麼我們要從貪心演算法講起。

從貪心到動態規劃的思考路徑#

flowchart TD
    A[貪心演算法] -->|局部最優 ≠ 整體最優| B[加入回溯]
    B -->|效率太低| C[遞迴窮舉]
    C -->|"時間複雜度 O(2ⁿ)"| D[發現重叠子問題]
    D -->|加入備忘錄| E[記憶化搜尋]
    E -->|自底向上| F[動態規劃]

    A -.- A1[只看當前最優]
    B -.- B1[可以退一步]
    C -.- C1[嘗試所有組合]
    E -.- E1[消除重複計算]
    F -.- F1[最優效率]

    style A fill:#ffebee
    style B fill:#fff3e0
    style C fill:#fff9c4
    style E fill:#e3f2fd
    style F fill:#e8f5e9

下一節，我們將深入探討如何從暴力遞迴演進到動態規劃。

Backward 動態規劃 從暴力到DP Forward