https://leetcode.com/problems/count-of-integers/
這題一開始我往 digital root 的方向去想，但是發現思路似乎錯了，而且 num 的範圍超過了 long long int，完全不知道如何下手。看到解答後整個茅塞頓開，這題非常有趣。
這題可以分成兩個部分，先求小於等於 num2 並且滿足條件的數字個數，然後再減去小於等於 num1 並且滿足條件的數字個數，最後再檢查 num1 本身是否滿足條件。
（如果這一題的 num1, num2 都是數字的話，可以減去小於等於 num1 - 1 中滿足條件的個數就好）
來看一個範例， num = "268"，要怎麼找到滿足條件的個數呢？
可以從最高位數開始，建造出一個新的 string，並且當這個 string 建造完成時，檢查其是否滿足條件。
首先第一位可以填 0, 1, 2（不能超過 2），那麼第二位可以填哪一些呢？
如果第一位是填 0, 1，那第二位可以隨便填，也就是 0 到 9 都可以填，因為不管後面怎麼填，都不會超過 268。但是如果第一位是填 2 的話，那麼第二位只能填 0, 1, 2, 3, 4, 5, 6（不能超過 6）。
最後是第三位，如果前面填 26 的話，第三位只能填 0, 1, 2, 3, 4, 5, 6, 7, 8（不能超過 8），其他情況都可以隨便填入 0 到 9。
我們再用一個 boolean 來記錄是否可以隨便填數字，然後使用 dp 來解。
這個時候可以寫下 dp 的關係式了dp[i][flag][sum] = 前 i 位(1 indexed)的和為 sum，並且接下來 （可以/不可以）隨便填數字，有多少種填數字的方法使得 digit sum 滿足條件flag = 1 代表不能隨便填數字，也就是第 i 位只能填 0 到 num[i] - '0'。flag = 0 代表可以隨便填數字，也就是 0 到 9 都可以填。
dp[i][0][sum] = dp[i + 1][flag][sum + j] for j from 0 to 9dp[i][1][sum] = dp[i + 1][0][sum + j] for j from 0 to (num[i] - '0' - 1) + dp[i + 1][1][sum + num[i] - '0']
一樣用上面的例子來看，
dp[0][1][0] 就是什麼都還沒填，並且不能隨便填數字的情況下，有多少數字滿足條件。
而他的關係式 dp[0][1][0] = dp[1][0][0] + dp[1][0][1] + dp[1][1][2]，也就是計算填入 0 (dp[1][0][0])，填入 1 (dp[1][0][1])，填入 2 (dp[1][1][2]) 的總和。
int mod = 1e9 + 7;
int count(string num1, string num2, int min_sum, int max_sum) {
int cnt = 0;
for (char c: num1){
cnt += c - '0';
}
if (cnt >= min_sum && cnt <= max_sum){
cnt = 1;
}
else {
cnt = 0;
}
int ans = under(n2, min_sum, max_sum) - under(n1, min_sum, max_sum) + cnt;
ans = (ans + mod) % mod;
return ans;
}
int under(string &num, int min_sum, int max_sum){
int memo[24][2][401];
memset(memo, -1, sizeof(memo));
function<int(int, int, int)> dp = [&](int index, int flag, int sum){
if (index == num.size()){ // 已經填完了，檢查是否符合條件
if (sum >= min_sum && sum <= max_sum){
return 1;
}
else {
return 0;
}
}
if (memo[index][flag][sum] != -1){ // 計算過的問題，直接回傳結果
return memo[index][flag][sum];
}
int maxi = 9;
if (flag == 1){ // 如果不能隨便填的話，最多只能填 num[index] - '0'
maxi = num[index] - '0';
}
int cnt = 0;
for (int i = 0; i <= maxi; i++){
if (flag == 1 && i == num[index] - '0')
cnt = (cnt + dp(index + 1, 1, sum + i)) % mod;
else
cnt = (cnt + dp(index + 1, 0, sum + i)) % mod;
}
memo[index][flag][sum] = cnt;
return cnt;
};
return dp(0, 1, 0);
}
time complexity: $O(n \times m)$
space complextiy: $O(n \times m)$
where n = num.size(), m = max_sum