Digit Dynamic Programming

数位 DP

灵神视频

数位是指把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 0~9，其他进制可类比十进制。

数位 DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：

  1. 要求统计满足一定条件的数的数量（即，最终目的为计数）；
  2. 这些条件经过转化后可以使用「数位」的思想去理解和判断；
  3. 输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
  4. 上界很大（比如 10^{18}），暴力枚举验证会超时。

数位 DP 的基本原理：

考虑人类计数的方式，最朴素的计数就是从小到大开始依次加一。但我们发现对于位数比较多的数，这样的过程中有许多重复的部分。例如，从 7000 数到 7999、从 8000 数到 8999、和从 9000 数到 9999 的过程非常相似，它们都是后三位从 000 变到 999，不一样的地方只有千位这一位，所以我们可以把这些过程归并起来，将这些过程中产生的计数答案也都存在一个通用的数组里。此数组根据题目具体要求设置状态，用递推或 DP 的方式进行状态转移。

数位 DP 中通常会利用常规计数问题技巧，比如把一个区间内的答案拆成两部分相减（即 {[l, r]} = {[0, r]}-_{[0, l - 1]}）

那么有了通用答案数组，接下来就是统计答案。统计答案可以选择记忆化搜索，也可以选择循环迭代递推。为了不重不漏地统计所有不超过上限的答案，要从高到低枚举每一位，再考虑每一位都可以填哪些数字，最后利用通用答案数组统计答案。

2719. 统计整数数目

方法一：数位DP

题解

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
class Solution {

    int min_sum, max_sum, n, MOD = (int) (1e9 + 7);
    int[][] dp;

    public int count(String num1, String num2, int min_sum, int max_sum) {
        this.min_sum = min_sum;
        this.max_sum = max_sum;
        int res = count(num2) - count(num1) + MOD;
        int temp = count(num2);
        int sum = 0;
        for (int i = 0; i < num1.length(); ++i)
            sum += num1.charAt(i) - '0';
        if (sum >= min_sum && sum <= max_sum)
            ++res;
        return res % MOD;
    }

    private int count(String num) {
        n = num.length();
        dp = new int[n][401];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(num, 0, 0, true);
    }

    private int dfs(String num, int index, int preSum, boolean isLimit) {
        if (preSum > max_sum)
            return 0;
        if (index == num.length())
            return preSum >= min_sum ? 1 : 0;
        if (!isLimit && dp[index][preSum] != -1)
            return dp[index][preSum];
        int upperBound = isLimit ? num.charAt(index) - '0' : 9;
        int res = 0;
        for (int i = 0; i <= upperBound; ++i)
            res = (res + dfs(num, index + 1, preSum + i, isLimit && i == upperBound)) % MOD;
        if (!isLimit)
            dp[index][preSum] = res;
        return res;
    }
}

2376. 统计特殊整数

方法一：数位DP

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
class Solution {
    int n;
    int[][] dp;
    String num;

    public int countSpecialNumbers(int n) {
        num = String.valueOf(n);
        this.n = num.length();
        dp = new int[this.n][1 << 10];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(0, 0, true, false);
    }

    private int dfs(int index, int mask, boolean isLimit, boolean isNum) {
        if (index == n)
            return isNum ? 1 : 0;// isNum 为 true 表示得到了一个合法数字
        if (!isLimit && isNum && dp[index][mask] != -1)
            return dp[index][mask];
        int res = 0;
        if (!isNum) // 可以跳过当前数位 (继续填0)
            res += dfs(index + 1, mask, false, false);
        // 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）
        int upperBound = isLimit ? num.charAt(index) - '0' : 9; 
        // 如果isNum,是前导0，那么i从0开始；否则不是前导0，i从1开始
        for (int i = isNum ? 0 : 1; i <= upperBound; ++i)
            if ((mask >> i & 1) == 0) // d 不在 mask 中
                res += dfs(index + 1, mask | 1 << i, isLimit && i == upperBound, true);
        if (!isLimit && isNum)
            dp[index][mask] = res;
        return res;
    }
}

233. 数字 1 的个数

方法一：数位DP

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
class Solution {
    int n;
    int[][] dp;
    String num;

    public int countDigitOne(int n) {
        num = String.valueOf(n);
        dp = new int[num.length()][9];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        this.n = num.length();
        return dfs(0, 0, true);
    }

    private int dfs(int index, int count, boolean isLimit) {
        if (index == n)
            return count;
        if (!isLimit && dp[index][count] != -1)
            return dp[index][count];
        int res = 0, cur = num.charAt(index) - '0';
        int upperBound = isLimit ? cur : 9;
        for (int i = 0; i <= upperBound; ++i)
            res += dfs(index + 1, count + (i == 1 ? 1 : 0), isLimit && i == upperBound);
        if (!isLimit)
            dp[index][count] = res;
        return res;
    }
}

面试题 17.06. 2出现的次数

方法一：数位DP

把上一题的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
class Solution {
    int n;
    int[][] dp;
    String num;

    public int numberOf2sInRange(int n) {
        num = String.valueOf(n);
        dp = new int[num.length()][9];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        this.n = num.length();
        return dfs(0, 0, true);
    }

    private int dfs(int index, int count, boolean isLimit) {
        if (index == n)
            return count;
        if (!isLimit && dp[index][count] != -1)
            return dp[index][count];
        int res = 0, cur = num.charAt(index) - '0';
        int upperBound = isLimit ? cur : 9;
        for (int i = 0; i <= upperBound; ++i)
            res += dfs(index + 1, count + (i == 2 ? 1 : 0), isLimit && i == upperBound);
        if (!isLimit)
            dp[index][count] = res;
        return res;
    }
}

1012. 至少有 1 位重复的数字

方法一：数位DP

n - 2719. 统计整数数目返回的结果

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
class Solution {
    public int numDupDigitsAtMostN(int n) {
        return n - countSpecialNumbers(n);
    }

    int n;
    int[][] dp;
    String num;

    public int countSpecialNumbers(int n) {
        num = String.valueOf(n);
        this.n = num.length();
        dp = new int[this.n][1 << 10];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(0, 0, true, false);
    }

    private int dfs(int index, int mask, boolean isLimit, boolean isNum) {
        if (index == n)
            return isNum ? 1 : 0;// isNum 为 true 表示得到了一个合法数字
        if (!isLimit && isNum && dp[index][mask] != -1)
            return dp[index][mask];
        int res = 0;
        if (!isNum) // 可以跳过当前数位 (继续填0)
            res += dfs(index + 1, mask, false, false);
        // 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）
        int upperBound = isLimit ? num.charAt(index) - '0' : 9; 
        // 如果isNum,是前导0，那么i从0开始；否则不是前导0，i从1开始
        for (int i = isNum ? 0 : 1; i <= upperBound; ++i)
            if ((mask >> i & 1) == 0) // d 不在 mask 中
                res += dfs(index + 1, mask | 1 << i, isLimit && i == upperBound, true);
        if (!isLimit && isNum)
            dp[index][mask] = res;
        return res;
    }
}

600. 不含连续1的非负整数

方法一：数位DP

注意：res += dfs(index + 1, i, isLimit && i == upperBound);不要把i写成cur！！！

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
class Solution {
    int length;
    int[][] dp;
    String num;

    public int findIntegers(int n) {
        num = Integer.toBinaryString(n);
        length = num.length();
        dp = new int[length][2];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(0, 0, true);
    }

    private int dfs(int index, int pre, boolean isLimit) {
        if (index == length)
            return 1;
        if (!isLimit && dp[index][pre] != -1)
            return dp[index][pre];
        int res = 0, cur = num.charAt(index) - '0';
        int upperBound = isLimit ? cur : 1;
        for (int i = 0; i <= upperBound; ++i) {
            if (pre == 1 && i == 1)
                continue;
            res += dfs(index + 1, i, isLimit && i == upperBound);
        }
        if (!isLimit)
            dp[index][pre] = res;
        return res;
    }
}

902. 最大为 N 的数字组合

方法一：数位DP

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
class Solution {
    String[] digits;
    int length, n;
    String num;
    int[] dp;
    public int atMostNGivenDigitSet(String[] digits, int n) {
        this.n = n;
        this.digits = digits;
        num = String.valueOf(n);
        length = num.length();
        dp = new int[length];
        Arrays.fill(dp, -1);
        return dfs(0,  true, false);
    }

    private int dfs(int index, boolean isLimit, boolean isNum) {
        if (index == length)
            return isNum ? 1 : 0;
        if (!isLimit && isNum && dp[index] != -1)
            return dp[index];
        int res = 0, cur = num.charAt(index) - '0';
        if (!isNum)
            res += dfs(index + 1,  false, false);
        for (String x : digits) {
            int val = Integer.parseInt(x);
            if (isLimit && val > cur)
                break;
            res += dfs(index + 1, isLimit && val == cur, true);
        }

        if (!isLimit && isNum)
            dp[index] = res;
        return res;
    }
}

1397. 找到所有好字符串

Algorithms > Dynamic Programming
#动态规划
Digit Dynamic Programming
https://leopol1d.github.io/2023/07/30/digit-dynamic-programming/
作者
Leopold
发布于
2023年7月30日
许可协议