數位動態規劃（digit DP）

有些計數問題問「從 0 到 N 之間有多少個數具有性質 P？」——例如，十億以下有多少整數不含數字 7，或各位數字之和是 3 的倍數。N 可能極大（數百位），所以你不可能一個一個地遍歷每個數。數位動態規劃就是用來計數這類數字的技術：從最高位到最低位、一位一位地把數字建出來，並只記住關於前綴足以判斷 P 是否仍可能滿足的資訊。

你由左至右處理 N 的各位，且在每個位置決定要放哪個數字。狀態攜帶幾項資訊。最關鍵的旗標是「貼緊（tight）」：到目前為止所選的數字是否恰好等於 N 的前綴？若 tight 為真，下一位不能超過 N 在此位置的數字（否則會超過 N）；若 tight 為假（你已放了較小的東西），下一位就可以自由地是 0 到 9 的任意值。除了 tight，你還儲存 P 所需的任何東西——對某數取模的累計位數和、某種計數、最後一位數字、「是否已見過非零數字」的前導零旗標等等。定義 dp[pos][tight][...其他狀態...] 為填滿位置 pos..結尾的有效方法數。轉移讓數字 d 在其允許範圍內（不 tight 時為 0..9，tight 時為 0..N[pos]）做迴圈，並以更新後的 tight 遞迴到 pos+1（只有當你放的恰好是 N 的數字時才保持 tight）。對非 tight 的情況以 (pos, 性質狀態) 記憶化，因為 tight 的情況每個位置至多發生一次。

若 N 有 L 位，大約有 L 個位置乘以（一個小的性質狀態）乘以 2（tight），每個試 10 個數字，所以數位動態規劃的時間大致正比於 L 乘以性質狀態大小乘以 10——對位數而言是多項式，即使 N 本身大得驚人。這正是重點：它把「數到 10^L」轉成正比於 L 的工作量。經典的坑是前導零的處理（像 007 其實是 7，所以「是否已開始」旗標常很重要），以及用 f(B) - f(A-1) 回答區間查詢 [A, B]，其中 f(x) 計數 [0, x] 中的有效數字。