動態規劃（Digit DP）是什麼？新手指南

更新日期： 2025 年 3 月 7 日

假設你想要算：「在 0 到一個『上限數字』之間，符合某些條件的數字有幾個？」

• 例如：從 0 到 99999 之間，有多少數字的『每個位數都不包含 7』？
• 或者：從 0 到 12345 之間，有多少數字的『位數加起來等於 9』？

這類問題如果用「把每個數字都拿出來檢查」的方法，當上限很大時，電腦就會超級慢。

於是「數位 DP」就是一種用位數拆開，再配合動態規劃的方法，加速解決的技巧。

什麼是「位數拆開」？

想像我們「一位一位」處理

把上限數字寫成好幾位：例如「10000」，就想成 5 位：

我們想要逐位「決定」要填什麼數字，最後組出一個完整的數字。

為什麼要管「有沒有超過上限」？

如果我們要算的範圍是從 0 ～ 10000，那麼只要我們一旦選了一個「超過 10000」的數字，就不能算了。

所以在每一位做決定時，我們都要先確定：

• 目前是否還跟「10000」的對應位完全一樣？
• 還是已經比「10000」更小了？
• 還是已經超過「10000」？（那就直接不能用）

運作邏輯

• 上限數字是 4321（4 位數）。

• 我們逐位填入數字，從高位到低位。
• 目標是構造所有不超過 4321 的合法數字。

初始化

• 起始情況：當前數字為空 ("")，處於「與上限保持一致」的狀態。

第一位（最高位）處理

上限數字的第一位是 4。

在「保持一致」的狀態下，我們只能選擇 0, 1, 2, 3, 4（不能超過 4）：

• 選 0 到 3： 一旦選了這些數字，進入「比上限小」的狀態。

• 選 4： 繼續保持「與上限一致」的狀態。

第二位處理

• 當前數字可能是：0、1、2、3（已經比上限小）和 4（保持一致）。

當數字是 4（保持一致）

第二位只能選 0, 1, 2, 3（因為上限的第二位是 3）：

• 選 0, 1, 2： 進入「比上限小」的狀態。

• 選 3： 繼續保持「與上限一致」。

• 選 4 及以上： 直接跳過，這條路徑無效（會超過上限）。

當數字是 0, 1, 2, 3（已經比上限小）

• 第二位可以自由選擇 0 到 9，不受上限約束。

第三位處理

若前兩位是 43（保持一致），上限的第三位是 2：

• 選 0, 1： 進入「比上限小」的狀態。

• 選 2： 繼續保持「與上限一致」。

• 選 3 及以上： 直接跳過，無效路徑。

• 其他數字（例如 40, 32, 21…），已經比上限小，可以自由選擇 0 到 9。

第四位（最低位）處理

若前三位是 432，上限的第四位是 1：

• 選 0： 比上限小，合法。

• 選 1： 剛好等於上限，仍然合法。

• 選 2 及以上： 超過上限，無效路徑。

• 其他情況（例如 430, 329），已經比上限小，依然可以自由選擇 0 到 9。

這樣的做法有什麼好處？

• 不需要遍歷從 0 到 4321 所有數字，而是通過「逐位選擇」的方式，有效減少了無效數字的計算。
• 當上限很大時，時間複雜度不再是 O(上限)，而是 O(位數 × 狀態數)，效率大大提高。

「小心模式」 vs. 「自由模式」是什麼？

在數位 DP（數字動態規劃）中，「小心模式」和「自由模式」是一種用來描述當前狀態的概念。

它們幫助我們在逐位填數字時，靈活地應對不同情況，確保構造出的數字既符合題目條件，又不會超過上限。

小心模式 (smaller = 0)

🟡 什麼是小心模式？

• 小心模式表示：當前構造的數字每一位都精確地和上限對應位保持一樣。
• 在這種情況下，我們必須「小心翼翼」地填入下一位數字，不能超過上限對應位允許的數值。

行為規則

• 只能填入和上限對應位一樣或更小的數字。
• 如果填入的數字剛好等於上限對應位，則繼續保持「小心模式」。
• 如果填入的數字比上限對應位小，會切換到「自由模式」，接下來的位數不再受上限限制。

例子：上限是 10000

• 當前構造數字是 1----（已經填入 1，和上限的第一位相同）。
• 下一位上限是 0，那麼這一位只能選擇 0，保持「小心模式」。
• 如果填入 0，數字變成 10---，還是「小心模式」。
• 如果選擇 0 以外的數字（例如 1 或更大），這一條路徑就無效，因為超過了上限。

自由模式 (smaller = 1)

🟢 什麼是自由模式？

• 自由模式表示：在之前的某一位，我們已經填入了比上限對應位更小的數字。
• 進入自由模式後，後續位數的選擇就完全不再受上限的限制，可以任意填 0 到 9。

行為規則

• 在自由模式下，沒有「不能超過上限」的限制。
• 可以靈活填入任何數字，僅需考慮題目的其他特定條件（如「不能有 7」或「數字和等於 9」等）。
• 這種模式通常能大幅降低計算複雜度，因為選擇範圍更廣，無需逐位對比上限。

例子：上限是 9999

• 假設在第一位我們填入了 8（比上限的 9 小），數字變成 8---。
• 因為 8 < 9，我們立即進入自由模式。
• 後續的每一位都可以自由填 0 到 9，比如填 8, 5, 3，最終得到數字 8853，依然小於 9999。

模式轉換：小心模式 ➡️ 自由模式

🚦什麼情況會從小心模式轉成自由模式？

1. 當填入的數字比上限對應位小：
   • 例如上限是 4321，當前已填 4 和 3，接下來對應位是 2：
     • 如果填入 1（比 2 小），則轉入自由模式。
     • 接下來的位數可以自由填 0 到 9。
2. 當前位已經是「自由模式」時，自然保持自由模式：
   • 一旦進入自由模式，後續位數不再需要與上限對比，直到填滿所有位數。

無效情況：超過上限的分支（剪枝）

❌什麼時候直接跳過這條路徑？

• 如果在「小心模式」中填入了比上限對應位更大的數字，這條路徑直接無效：
  • 例如上限是 4321，當前數字是 43--：
    • 如果當前位只能填 2，卻填了 3，就會得到 433-，超過上限，這條路徑立刻被剪枝（停止計算）。

模式控制的核心邏輯

數位 DP 的樹狀圖結構

數位 DP（數字動態規劃）的核心是在逐位填數字的過程中，構建出一棵決策樹（Decision Tree）。

每個節點代表當前構造出的部分數字，每條邊則代表填入某一位數字的選擇。

樹狀圖的基本構造：

• 根節點（Root）：從空字串開始，代表還沒有填入任何數字。
• 中間節點（Intermediate Nodes）：每填入一位數字，就從父節點延伸出一個子節點。
• 葉節點（Leaf Nodes）：所有位數都填滿，構造出一個完整的數字。

graph TD
    Root["根節點 (空字串)"] --> N01["填入 0-3 (< 4)"]
    Root --> N02["填入 4 (= 4)"]
    
    %% 自由模式分支
    N01 --> FreeMode["自由模式 (smaller = 1)"]
    FreeMode --> F0["可填入 0-9 任意數字"]
    F0 --> F00["..."]
    F0 --> F01["..."]
    F0 --> F02["..."]
    
    %% 小心模式分支
    N02 --> CarefulMode["小心模式 (smaller = 0)"]
    CarefulMode --> C0["只能填入 0-3 (≤ 上限第二位)"]
    C0 --> C00["填入 0-2 (< 3): 進入自由模式"]
    C0 --> C01["填入 3 (= 3): 保持小心模式"]
    
    %% 第三層
    C01 --> C10["只能填入 0-2 (≤ 上限第三位)"]
    C10 --> C100["填入 0-1 (< 2): 進入自由模式"]
    C10 --> C101["填入 2 (= 2): 保持小心模式"]
    
    %% 剪枝示意
    CarefulMode -.-> Prune1["剪枝: 填入 > 3 的數字"]
    C01 -.-> Prune2["剪枝: 填入 > 2 的數字"]
    
    %% 樣式
    classDef free fill:#9fd6a5,stroke:#333,stroke-width:1px;
    classDef careful fill:#ffcc80,stroke:#333,stroke-width:1px;
    classDef prune fill:#ff8a80,stroke:#333,stroke-width:1px,stroke-dasharray: 5 5;
    
    class FreeMode,F0,F00,F01,F02,C00,C100 free;
    class CarefulMode,C0,C01,C10,C101 careful;
    class Prune1,Prune2 prune;
    

小心模式（smaller = 0）在樹狀圖中的表現

在樹上的行為

• 從根節點開始，第一層的分支會受上限數字的第一位限制。
• 每一個「小心模式」的節點，向下一層延伸分支時，只有數字不超過對應位的選擇才會生成新的子節點。

舉例：上限是 4321

1. 第一位數：只能選 0, 1, 2, 3, 4（上限第一位是 4）：
   • 填 0, 1, 2, 3：進入「自由模式」（比 4 小）。
   • 填 4：保持「小心模式」。
2. 第二位數（保持小心模式時）
   • 當前數字是 4，上限的第二位是 3：
   • 只能選 0, 1, 2, 3：
     • 填 3：仍然保持「小心模式」。
     • 填 0, 1, 2：轉入「自由模式」。
     • 填 4 或更大：超過上限，直接剪枝，這條分支不會延伸出子節點。

自由模式（smaller = 1）在樹狀圖中的表現

在樹上的行為

• 一旦進入「自由模式」，當前節點可以生成 0 到 9 共 10 個分支。
• 這些分支不再受上限的每一位限制，唯一需要考慮的只是題目中的其他數字條件（例如「不能有 7」等）。

舉例：上限是 4321

1. 第一位數填 3（比 4 小），進入自由模式：
   • 第二位數可以是 0 到 9，每一個選擇都能生成一個新節點。
   • 每個節點再向下拓展時，依然是 0 到 9 的全選擇。
2. 直到達到最底層（葉節點）：
   • 例如從 3--- 到 3091、3874 等數字，都會是合法的。

剪枝的意涵：為什麼和怎麼剪？

剪枝（Pruning）的定義

• 剪枝是在決策樹中，提前終止某些無效的分支，避免不必要的計算。
• 在數位 DP 中，當發現某一分支必然無法構造出有效數字時，直接跳過該分支及所有子節點。

剪枝的應用場景

1. 小心模式中填入數字超過上限對應位時
   • 例如當前數字是 43--，上限是 4321，此時第三位只能選 0, 1, 2：
   • 若嘗試填入 3 或更大，會產生超過 4321 的數字，這條分支直接剪枝。
2. 遇到違反特定題目條件的情況
   • 例如題目要求「數字中不能包含 7」，如果填入 7，也可以立即剪枝。

剪枝的好處

• 極大地減少樹狀圖中的節點數量。
• 優化時間複雜度，尤其是在上限很大（如 10^18 級別）時，避免爆炸性的計算量。

動態規劃表（DP 表）怎麼記？，

在很多程式解法裡，會用個「dp 狀態」去記錄：

• dp[pos][smaller][其他條件…] = 某個統計結果
• pos 表示現在正在填哪一位（從左到右數第幾位）。
• smaller=0 或 1 表示現在是「小心模式」還是「自由模式」。
• 其他條件… 可能是你題目想要的其他限制（例如位數加起來多少、或者是否出現某個數字等等），這就看題目需求。

「DP」這個表就是為了避免重複計算：

最後把結果累積起來，就能算出所有可能的答案。

我們在第 pos 位、處於 smaller=0 或 1、並且滿足某些條件的情況下，可以選哪些數字？

選完之後，下個階段會變成什麼新狀態？

先把「位數」拆開，並加上「leading zeros」觀念

當我們說 pos 是「現在正在填哪一位」，我們通常會約定：

1. 從「最左邊那位」編號開始，一直到「最右邊」為止。
2. 如果上限的位數是 L，那麼 pos 會從 0（或 1）一路處理到 L−1（或 L）。
3. 即使有些數字比 L 位更短（例如 123 只有 3 位，但上限 10000 有 5 位），我們會在比較左側時，自動把它當成「前面補很多 0」，好比 00123。

這樣做的好處是：

• 你處理「第 0 位」就是「最左邊」那一位，即便實際上你選擇了 0，也可以表示「本來這位數就沒有用到」。
• 可以確保每個數字都用固定長度來看待，方便 DP。

dp[pos][smaller][其他條件] 是什麼

這個表通常是個「三維」或更多維度的陣列（array）：

• pos：整數，代表「正在填第幾位」。
• smaller：布林值（0 或 1），表示「到目前為止，我填的數字前綴，是否已經小於上限」？
  • 0 = 還沒有小於上限（即「小心模式」），
  • 1 = 已經小於上限（即「自由模式」）。
• 其他條件：根據題目要求，可能會加上更多變數，如「目前位數的和除以 K 的餘數是什麼？」「已經用過幾次數字 7？」等等。這些是可選的。

dp[pos][smaller][…] 是什麼意義？

它可以代表不同的「統計或判斷結果」，常見有兩類：

1. 計算「有幾種方法」：
   • 代表「從第 pos 位到最後，如果我現在所處的『smaller 狀態』是某值，並符合之前的其他條件，那麼『能產生多少個有效數字』？」
   • 最後結果往往是 dp[0][0][…]（表示「從最左邊第一位開始，還沒小於上限」）的值，告訴你總共有幾個符合條件的數。
2. 計算「符合條件的總和」或「最小值/最大值」：
   • 也有人用類似方法來算「所有符合的數之和」，就會在 dp 狀態裡存「該條件能產生的數字總和」；或存「能不能達到某種目標」的布林值等等。
   • 依題目而變，原理都類似。

為何需要 DP 來「避免重複計算」？

什麼是「重複計算」？

當你用一種「自上而下的搜尋」（深度優先搜尋，DFS）來逐位填數字時，你可能會遇到相同的狀態多次。

這意味著你在不同的計算路徑中，會對相同的問題進行重複運算。

舉個例子

假設我們的上限數字是 4321，你在構造數字的過程中，有可能多次遇到同樣的情況：

• 當前位數 (pos) 是第 2 位。
• 目前在「自由模式」（smaller = 1，已經比上限小）。
• 位數和（或其他條件，例如位數加總）是 5。

如果你的搜尋過程中，不同的路徑都進入了這個完全相同的狀態，每次都從頭開始計算，這會導致重複工作，浪費大量時間。

「記憶化」的概念：用 DP 陣列避免重複計算

🗂️ 什麼是「記憶化」（Memoization）？

• 記憶化是一種把已經計算過的結果存起來的技巧，當再次遇到相同情況時，直接調用已經計算過的值。
• 在數位 DP 中，我們使用一個DP 陣列（通常是多維陣列）來記錄每個「狀態」的結果。

如何操作？

1. 計算時先查表：當進入 (pos, smaller, ...) 狀態時，先查看 DP 陣列中這個位置是否已有值。
2. 已經計算過的話，直接返回：如果 DP 陣列中有值，說明這個狀態之前已經完整計算過，直接返回該值，避免重複計算。
3. 沒有計算過的話，進行計算，並記錄結果：如果 DP 陣列中是空的，說明這是新的狀態，需要遞迴計算所有可能的選擇，並將結果存入 DP 陣列，方便未來調用。

簡單比喻：岔路的選擇

這就像在迷宮中行走，每次走到一個交叉口，如果你之前已經標註過「往左是死路」，那麼下次再來到這裡時，你可以直接選擇往右，而不用再走一遍死路。

🔁 「狀態」和「轉移」：一步接一步地推進

1. 什麼是「狀態」？

「狀態」是用來描述當前計算所處的具體位置和情況。在數位 DP 中，一個狀態通常由多個變量組成，例如：

(pos, smaller, sum_of_digits, other_conditions)

• pos：當前處於數字的第幾位（從高位到低位）。
• smaller：是否已經進入「自由模式」（0 = 小心模式，1 = 自由模式）。
• sum_of_digits（可選）：目前填入的數字位數和，這是特定題目中的條件之一。
• other_conditions（可選）：其他特定題目要求的條件，例如「數字中不能有7」等。

什麼是「轉移」？

「轉移」是指從當前狀態選擇一個數字，進而轉移到下一個狀態的過程。

狀態轉移的具體步驟

• 當前狀態是 (pos, smaller, sum_of_digits)。
• 當前位數是 pos，我們需要決定填入哪個數字 (digit)。

🧮 根據模式選擇數字

1. 小心模式（smaller = 0）
   • 當前位的數字 (digit) 只能在 0 ~ limit_digit 之間選擇（limit_digit 是上限數字對應位的數字）。
   • 如果選擇 digit < limit_digit，會轉入「自由模式」。
   • 如果選擇 digit == limit_digit，保持「小心模式」。
2. 自由模式（smaller = 1）
   • 當前位的數字可以自由選擇 0 ~ 9，不受上限影響。

➡️ 轉移到下一個狀態

• 下一個狀態變為 (pos + 1, new_smaller, new_sum_of_digits)。
  • pos + 1：進入下一位數字。
  • new_smaller：根據選擇的數字更新模式（保持或進入自由模式）。
  • new_sum_of_digits：位數和加上選擇的數字。

數位 DP 計算流程的詳細解說

初始化：設定初始狀態

開始之前的準備

• 上限數字：假設上限數字是 4321，這是一個 4 位數字。
• DP 陣列（dp[pos][smaller][其他條件]）：用於記錄不同狀態下已經計算過的結果，以避免重複計算。

❓ 第 0 位是什麼意思？

• 在數位 DP 中，位數的編號是從左到右、從 0 開始計數的。
• 因此，當 pos = 0 時，表示我們處於數字的最高位，也就是最左邊的數字。

以 4321 為例

• 當 pos = 0 時，我們還沒有選擇任何數字，相當於在數字構造的最初狀態，類似於一個空白字串 ("")。
• 隨著 pos 增加，我們會逐位填入數字，直到到達數字的最後一位（pos = 3 對於 4 位數字）。

初始狀態的設定

• pos = 0：處於數字的第 0 位，準備填入第一個數字（最高位）。
• smaller = 0：當前處於「小心模式」，後續填數字時需小心不能超過上限的對應位。
• 其他條件（依題目而定）：
  • sum_mod = 0：初始位數和設為 0。
  • not_used_7 = True：表示當前構造的數字中尚未出現 7。

❓ 那麼 dp[0][0][...] 是什麼意思？

• dp[0][0][...] 代表：
  • 從數字的第 0 位開始（數字還是空白字串）。
  • 處於小心模式（還沒有進入自由模式，填數字需要遵守上限限制）。
  • 滿足其他初始條件（例如 sum_mod = 0, not_used_7 = True）。
  • 最終能夠構造出符合題目條件的數字總數。

計算 dp[0][0][...]：填入第一位數字

選擇數字 (digit) 的範圍

• 在「小心模式」（smaller = 0）下，數字的選擇受到上限的約束。
• 例如，上限是 4321，第 0 位的上限數字是 4，所以我們可以選擇的數字是 0, 1, 2, 3, 4。

根據 digit 決定下一步的狀態

1. 選擇 digit < limit_digit 的情況

• 如果選擇 digit = 3（小於上限的 4），會進入「自由模式」。
• 下一步狀態是 dp[1][1][...]：
  • pos = 1：處於數字的第 1 位（填入下一個數字）。
  • smaller = 1：進入「自由模式」，接下來的數字可以自由選擇 0~9。
  • 其他條件根據當前選擇更新：
    • 例如 sum_mod = 3（初始 0 + 3）。
    • 例如 not_used_7 = True（因為選了 3 而不是 7）。

2. 選擇 digit == limit_digit 的情況

• 如果選擇 digit = 4（剛好等於上限的 4），保持「小心模式」。
• 進入狀態 dp[1][0][...]：
  • pos = 1：進入數字的第 1 位。
  • smaller = 0：繼續「小心模式」，後續數字選擇依然受限。
  • 其他條件更新：
    • sum_mod = 4（初始 0 + 4）。
    • not_used_7 = True（依然沒選 7）。

3. 選擇 digit > limit_digit 的情況（剪枝）

• 如果選擇 digit = 5（大於 4），會超過上限，這條路徑直接剪枝，不再遞迴計算。
• 例如 5000 超過 4321，這條分支立即返回 0，表示這裡不會有有效的數字組合。

逐步遞推：每一層都做「選擇 digit」的動作

🚦 自由模式 (smaller = 1) 的情況

• 進入自由模式後，數字選擇完全自由，範圍是 0 到 9。
• 例如，狀態是 dp[2][1][...]，代表從數字的第 2 位開始，可以填入任意數字。

⚠️ 小心模式 (smaller = 0) 的情況

• 每一位只能選擇 0 到「當前位的上限數字」之間的數字。
• 例如，上限是 4321，在第 2 位（對應 2），數字選擇範圍只能是 0, 1, 2。

達到最終位置 (pos = 數字位數長度)

• 當 pos = 4 時，表示已經構造出一個完整的數字。
• 判斷這個數字是否滿足額外條件：
  • 例如 sum_mod 是否符合題目中的特定條件。
  • 例如數字中是否不包含 7。
• 加總結果：
  • 如果符合條件，返回 1（這條分支有效）。
  • 如果不符合條件，返回 0（這條分支無效）。

記憶化：避免重複計算

• 當遞迴過程中再次遇到相同的 (pos, smaller, ...) 狀態時，直接從 dp 表中取出結果，而不重算。

最終結果：dp[0][0][...] 是答案

• dp[0][0][...] 中的值，表示從最左邊開始，還在小心模式，滿足其他條件時，所有合法數字的總數。
• 這個值就是整個數位 DP 計算的最終答案。

重點總結

1. 逐位（從左到右）跟上限比：
   • 若「還沒出現過比上限更小的位數」，就要小心，不能填超過上限對應位；
   • 一旦「某位數字填得比上限更小」，後面就自由填。
   • 如果「某位數字填得比上限更大」，就直接不可能了。
2. 動態規劃表（或稱記憶化搜索）主要是在記錄：
   • 「我現在處理到第幾位」
   • 「目前是不是已經比上限小了」
   • 「其他題目要求的條件」
   • 這樣才能把各種情況算清楚。

大致就是這樣，用「小心模式 vs. 自由模式」的概念，確保不會不小心超過上限，但也不會錯失一些確定小於上限的分支。