第一篇記錄算法的文章，來介紹下新學到的算法：Digit DP。
暴力解#
題目模版一般會長的像這樣：給定區間 \([L, R]\) 和一個函數 \(f(x) \to \{\texttt{True}, \texttt{False}\}\)，問在 \([L, R]\) 之間的正整數，滿足 \(f(x)\) 的數量有多少？
現在我們可以帶入一個真實的例子，在 \([L = 19, R = 9999]\) 區間，每一位數的總合 為 \(k = 23\) 的數字共有幾個？
暴力解用 C++ 代碼演示如下：
bool DigitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
int GetSatisfiedCount(int l, int r, int k) {
int satisfied_count = 0;
for (int num = l; num <= r; ++num)
if (DigitSum(num) == k)
++satisfied_count;
return satisfied_count;
}
constexpr int start = 19;
constexpr int end = 9'999;
constexpr int k = 23;
std::cout << GetSatisfiedCount(start, end, k);
而這樣的時間複雜度為：
$$ O(r - l) \cdot O(|\texttt{f}|) = O(r - l) \cdot \log(\texttt{num}), $$
若區間大小非常大，例如 \([0, 10^9]\)，暴力解不太現實。
重新思考#
那麼，該如何優化呢？首先定義：
\(S(R, k)\)：在 \([0, R]\) 滿足 \(f(x) = k\) 的數量，其中 \(f(x)\) 為 \(x\) 的數字總合。
可以推出，\(S(R) - S(L - 1)\) 為在 \([L, R]\) 滿足 \(f(x) \to
\texttt{True}\) 的數量。並且觀察因為 \(R = 9999\)，任何滿足條件的值最多只會有
\(n = 4\) 位數。現在我們試著將題目變成子問題：若在第一位填上 i _ _ _，會發現
在剩下的 \(n - 1 = 3\) 位數中，剩下 \(k - i\) 的餘額。
現在我們定義 \(dp(n, k)\)：在 \(n\) 位數當中，滿足 \(f\) 的數量，可得：
$$ dp(n, k) = \sum_{i = 0}^9 dp(n - 1, k - i). $$
並且定義終止條件：\(dp(0, 0) = 1\)。
但這出現了一個問題，若 \(R\) 不等於 \(10^n - 1\) 的值，那麼不能考慮所有 \(n\) 為數的數字，舉例來說，若 \(R = 3456\)，則我們不能考慮所有 4 位數的字， 更具體的說，任何在 \([3457, 9999]\) 區間滿足條件的數字都不應被計算進去，必需加 入適當的條件判斷。
我們可以加入一個 isTight 的布林值，判斷當前這一位數應不應該遵守開區間的邊界規
範，重新定義 \(dp(n, k, \texttt{isTight})\)，對於題目 \(S(R, k) = S(3456,
k)\)，我們可以針對在首位數填上不同數字分成以下三種情形討論：
- 填上 \(< 3\) 的數字，那麼剩下的 3 位數不再需要遵守邊界規範，可以自由的填上 \([0, 999]\) 而不會超過 \(3456\)。
- 填上 \(3\)，那麼剩下的三位數還是必需遵守邊界規範 \([0, 456]\)。
- 顯然地，我們不能在第一位數填上 \(> 3\) 的任何數字。
$$ \begin{aligned} S(R, k) &= S(3456, k) \\ &= dp(4, k, \texttt{isTight = True}) \\ &= \sum_{i = 0}^2 dp(4 - 1, k - i, \texttt{isTight = False}) \\ &+ dp(4 - 1, k - 3, \texttt{isTight = True}). \end{aligned} $$