2719. Count of Integers

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 9
dp[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]) 的總和。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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