数位统计DP

发表于 2022-05-29 更新于 2022-10-04 分类于 acwing算法基础课笔记 Artalk： loading...

动态规划

数位DP

题目介绍

传统做法

分析思路

分情况讨论

整体思路

若求区间 $[a,b]$ 中 $x,x\isin[0,9]$ 出现的次数

$count(n,x)$ 为 $[1,n]$ 中 $x$ 出现的次数

类似前缀和的思想

$ans=count(b,x)$ - $count(a$ - $1,x)$

如何实现方法 $\bold{count(n,x)}$ ?

还是分情况: 分别求出 $x$ 在每一位上出现的次数

举例说明，令 $x=1$

以上就是1在第4位上出现的次数，计算过程

然后求出在每一位上出现的次数，最后累加

边界情况

若枚举到数字 $x$ 在最高位时，情况(1)不存在
若枚举到数字 $x=0$ 时，需要注意前导零的问题: 不能从 $000$ 开始，应该从 $001$ 开始
注意，若枚举到数字 $x=0$ ，不用计算 $0$ 在最高位上出现的次数(非法)

代码实现

$Cpp$

C++代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10;

/*

001~abc-1, 999

abc
    1. num[i] < x, 0
    2. num[i] == x, 0~efg
    3. num[i] > x, 0~999

*/

int get(vector<int> num, int l, int r)
{
    int res = 0;
    for (int i = l; i >= r; i -- ) res = res * 10 + num[i];
    return res;
}

int power10(int x)
{
    int res = 1;
    while (x -- ) res *= 10;
    return res;
}

int count(int n, int x)
{
    if (!n) return 0;

    vector<int> num;
    while (n)
    {
        num.push_back(n % 10);
        n /= 10;
    }
    n = num.size();

    int res = 0;
    for (int i = n - 1 - !x; i >= 0; i -- )
    {
        if (i < n - 1)
        {
            res += get(num, n - 1, i + 1) * power10(i);
            if (!x) res -= power10(i);
        }

        if (num[i] == x) res += get(num, i - 1, 0) + 1;
        else if (num[i] > x) res += power10(i);
    }

    return res;
}

int main()
{
    int a, b;
    while (cin >> a >> b , a)
    {
        if (a > b) swap(a, b);

        for (int i = 0; i <= 9; i ++ )
            cout << count(b, i) - count(a - 1, i) << ' ';
        cout << endl;
    }

    return 0;
}

$Java$

import java.util.*;
import java.io.*;

class Main{
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws Exception {
        while (true) {
            String[] strs = cin.readLine().split(" ");
            int a = Integer.parseInt(strs[0]);
            int b = Integer.parseInt(strs[1]);
            if (a == 0 && b == 0) break; 
            if (a > b) {
                int tmp = a; a = b; b = tmp;
            }
            for (int i = 0; i < 10; ++i) {
                StringBuilder sb = new StringBuilder();
                sb.append(count(b, i) - count(a - 1, i));
                sb.append(" ");
                log.write(sb.toString());
            }
            log.write('\n');
        }
        
        log.flush();
        log.close();
        cin.close();
    }
    static int power10(int x) {
        int ans = 1;
        while (x-- > 0) ans *= 10;
        return ans;
    }
    static int get(List<Integer> num, int l, int r) {
        int res = 0;
        for (int i = l; i >= r; --i) {
            res = res * 10 + num.get(i);
        }
        return res;
    }
    static int count(int n, int x) {
        if (n == 0) return 0;
        List<Integer> num = new ArrayList<>(); // num 存储n
        while (n != 0) {
            num.add(n % 10);
            n /= 10;
        }
        n = num.size();
        int res = 0;
        // 边界情况3. 不能计算0在最高位的出现的次数，非法
        for (int i = n - 1 - (x==0?1:0); i >= 0; --i) {
            if (i < n - 1)  { // 情况(1)
                res += get(num, n - 1, i + 1) * power10(i);
                if (x == 0) res -= power10(i); // 枚举到x=0时, 考虑前导0的问题，从001开始
            }
            // 情况(2)
            if (num.get(i) == x) res += get(num, i - 1, 0) + 1;
            else if (num.get(i) > x) res += power10(i);
        }
        return res;
    }
}

记忆化搜索

完整代码

import java.util.*;
import java.io.*;

class Main{
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 8;
    static int[][] dp = new int[N][N];
    public static int f(int i, int cnt, boolean isLimit, boolean isNum, char[] s, int target) {
        if (i == s.length) return cnt;
        if (!isLimit && isNum && dp[i][cnt] >= 0) return dp[i][cnt];
        int res = 0;
        if (!isNum) {
            // 可以跳过
            res = f(i + 1, cnt, false, false, s, target);
        }
        for (int d = isNum ? 0 : 1, up = isLimit ? s[i] - '0' : 9; d <= up; ++d) {
            res += f(i + 1, cnt + (d == target ? 1 : 0), isLimit && d == up, true, s, target);
        }
        if (!isLimit && isNum) dp[i][cnt] = res;
        return res;
    }
    public static void main(String[] args) throws Exception {
        while (true) {
            char[] A, B;
            
            String[] strs = cin.readLine().split(" ");
            int a = Integer.parseInt(strs[0]);
            int b = Integer.parseInt(strs[1]);
            if (a == 0 && b == 0) break; 
            if (a > b) {
                int tmp = b; b = a; a = tmp;
            } 
            A = Integer.toString(a - 1).toCharArray();
            B = Integer.toString(b).toCharArray();
            
            for (int i = 0; i < 10; ++i) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < N; ++j) {
                    Arrays.fill(dp[j], -1);
                }
                int x1 = f(0, 0, true, false, B, i);
                for (int j = 0; j < N; ++j) {
                    Arrays.fill(dp[j], -1);
                }
                int x2 = f(0, 0, true, false, A, i);
                sb.append(x1 - x2);
                sb.append(" ");
                log.write(sb.toString());
            }
            log.write('\n');
        }
        
        log.flush();
        log.close();
        cin.close();
    }
    
}

数位统计DP-代码模板

来自灵茶山艾府

例题，leetcode2376. 统计特殊整数

如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。

给你一个正整数 $n$ ，请你返回区间 $[1, n]$ 之间特殊整数的数目。

示例 1：

输入：n = 20
输出：19
解释：1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。

n为待求的整数数字，s代表n转化后的字符串

本质是递归深搜， $f(i, mask, isLimit, isNum)$ ，可以用记忆化搜索的思想来优化

$\text{mask}$ 保存状态-已经填的数字，类似 bitMap 的思想，用一个 int 整形保存即可
$\text{isLimit}$ $isLimit$ 数字大小的限制，例如求 $[1,123]$ $[1, 123]$ 如果前面两位填写的12x，则第三位最多为3，即120~123
- 如果为 true ，代表前面所有数位的数字都是 $n$ 对应数位上的，则当前数位最多为s[i] - '0'
- 如果为 false，则无限制
考虑前导零 $\text{isNum}$ $isNum$ ，例如：010 是非法的，但是 10 是合法的 case
- 如果为 false ，代表之前数位没有填任何数字
- 1. 当前位继续跳过
  2. 填1-9数字
- 如果为 true ，代表之前填了数字，则可以填0-9

代码

class Solution {
    public int countSpecialNumbers(int n) {
        char[] cs = Integer.toString(n).toCharArray();
        return f(0, 0, true, false, cs);

    }
    public int f(int i, int mask, boolean isLimit, boolean isNum, char[] s) {
        if (i == s.length) return isNum ? 1 : 0;
        int res = 0;
        if (!isNum) { // 如果前面没有填数字，当前位可以跳过，或者从1开始
            res = f(i + 1, mask, false, false, s);
            /**
                isLimit 为什么是false？
                因为如果当前位选择跳过，则相当于 n = 1234, 当前是第三位，那么下一数位
                xxx0~xxx9，都可以
             */
        }
        // 当前数位的上限
        int upperBound = isLimit ? s[i] - '0' : 9;
        int lowerBound = isNum ? 0 : 1; // 前面没有填，从1开始，考虑前导0
        for (int d = lowerBound; d <= upperBound; ++d) {
            // 先判断mask保存的填过的数字有没有d，1为出现
            if ((mask >> d & 1) == 0) { // 没有d
                res += f(i + 1, mask | (1 << d), isLimit && d == upperBound, true, s);
            }
        }
        return res;
    }
}

记忆化，保存状态，优化时间复杂度

本题只需保存 $dp(i, mask)$ 这个状态， $\text{mask}$ 保存的是之前数位出现过的数字，只要对于当前数位 $i$ 有相同的 $\text{mask}$ ，在递归计算之后的数位得到的结果是相同的，可以记忆该结果，直接返回

1
2
3

if (!isLimit && isNum && dp[i][mask] > 0) return dp[i][mask];
// ...
if (!isLimit && isNum) dp[i][mask] = res;

为什么增加!isLimit && isNum 这个条件判断？

因为有大小限制(isLimit == true)或者之前数位没有填数字(isNum == false)，这样的状态，在整个递归搜索过程中，只会出现一次，没有必要保存下来

这样dp数组保存的，也就成了不受限制的(i, mask)状态的合法方案数

这套板子给出了一个考虑前导零和数字大小限制下，比较通用的代码编写思路

完整代码

public int f(int i, int mask, boolean isLimit, boolean isNum, char[] s, int[][] dp) {
    if (i == s.length) return isNum ? 1 : 0;
    if (!isLimit && isNum && dp[i][mask] > 0) return dp[i][mask]; 
    int res = 0;
    if (!isNum) { // 如果前面没有填数字，当前位可以跳过，或者从1开始
        res = f(i + 1, mask, false, false, s, dp);
        /**
                isLimit 为什么是false？
                因为如果当前位选择跳过，则相当于 n = 1234, 当前是第三位，那么下一数位
                xxx0~xxx9，都可以
             */
    }
    // 当前数位的上限
    int upperBound = isLimit ? s[i] - '0' : 9;
    int lowerBound = isNum ? 0 : 1; // 前面没有填，从1开始，考虑前导0
    for (int d = lowerBound; d <= upperBound; ++d) {
        // 先判断mask保存的填过的数字有没有d，1为出现
        if ((mask >> d & 1) == 0) { // 没有d
            res += f(i + 1, mask | (1 << d), isLimit && d == upperBound, true, s, dp);
        }
    }
    if (!isLimit && isNum) dp[i][mask] = res;
    return res;
}

相关例题

233. 数字 1 的个数

题目介绍

给定一个整数 $n$ ，计算所有小于等于 $n$ 的非负整数中数字 $1$ 出现的个数。

示例
输入：n = 13
输出：6
解释：1、10、11、12、13（其中11算作两次）

分析

同样的，定义 $f(i, cnt, isLimit, isNum)$ 表示从左向右第 $i$ 位及之后数位的合法方案个数，同样的

$\text{i}$ 代表当前数位
$\text{cnt}$ 为之前数位 $1$ 的个数
$\text{isLimit}$ 为数字大小的限制，表示当前数位的取值是否会受到 $n$ 的制约，若为 $\text{true}$ ，则当前数位最多为 s[i] - '0'
$\text{isNum}$ 表示之前数位是否填了数字，若为 $\text false$ ，则当前数位要么跳过（也不填），要么从 $1$ 开始，避免前导零

由于本题目前导零不影响结果，因此可以省去 $\text{isNum}$ 这个参数

本题，只需记忆化 $dp(i, cnt)$ 这个状态，因为当前数位之前如果有相同个数的 1 ，并且不受限制的话，递归下去计算的结果其实是一样的

例如：

n = 6666 66, i = 4
1100 xx
0011 xx
都是dp[4][2]

代码

class Solution {
    int[][] dp;
    char[] s;
    public int countDigitOne(int n) {
        s = Integer.toString(n).toCharArray();
        int m = s.length;
        dp = new int[m][m];
        for (int i = 0; i < m; ++i) Arrays.fill(dp[i], -1);
        return f(0, 0, true);
    }
    public int f(int i, int cnt, boolean isLimit) {
        if (i == s.length) return cnt;
        if (!isLimit && dp[i][cnt] >= 0) return dp[i][cnt];
        int res = 0;
        for (int d = 0, up = isLimit ? s[i] - '0' : 9; d <= up; ++d) {
            res += f(i + 1, cnt + (d == 1 ? 1 : 0), isLimit && d == up);
        }
        if (!isLimit) dp[i][cnt] = res;
        return res;
    }
}

788. 旋转数字

题目介绍

人话翻译：

核心问题：求 $[1, N]$ 中有多少个好数？

好数的所有数位不包括 3，4，7，并且至少有2，5，6，9其中一个

分析

同样的，本题前导零不影响结果，因此省去 $isNum$ 这个参数

构造 $f(i, isDiff, isLimit)$

$\text{isDiff}$ 表示之前数位是否至少包含 2,5,6,9 其中一个，取值为0,1 ，利用或运算的特点进行赋值，这样可以保证：只要有2,5,6,9中一个， $\text{isDiff}$ 就会被赋为 $1$ ，只有一个都没时，才会为 $0$
$\text{isLimit}$ 同样表示当前数位的取值是否会受到 $n$ 的限制

这里@灵茶山艾府的代码实现，巧妙创建了一个DIFFS数组

代码

class Solution {
    static final int[] DIFFS = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};

    char s[];
    int dp[][];

    public int rotatedDigits(int n) {
        s = Integer.toString(n).toCharArray();
        var m = s.length;
        dp = new int[m][2];
        for (var i = 0; i < m; i++) Arrays.fill(dp[i], -1);
        return f(0, 0, true);
    }

    int f(int i, int isDiff, boolean isLimit) {
        if (i == s.length) return hasDiff; // 只有包含 2/5/6/9 才算一个好数
        if (!isLimit && dp[i][hasDiff] >= 0) return dp[i][isDiff];
        var res = 0;
        var up = isLimit ? s[i] - '0' : 9;
        for (var d = 0; d <= up; ++d) // 枚举要填入的数字 d
            if (DIFFS[d] != -1) // d 不是 3/4/7
                res += f(i + 1, isDiff | DIFFS[d], isLimit && d == up);
        if (!isLimit) dp[i][isDiff] = res;
        return res;
    }
}

902. 最大为 N 的数字组合

题目介绍

给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如，如果 digits = ['1','3','5'] ，我们可以写数字，如 '13', '551', 和 '1351315'。

返回 可以生成的小于或等于给定整数 n 的正整数的个数。

1 <= digits.length <= 9
digits[i].length == 1
digits[i] 是从 '1' 到 '9' 的数
digits 中的所有值都不同
digits 按 非递减顺序 排列
1 <= n <= 109

输入：digits = ["1","3","5","7"], n = 100
输出：20
解释：
可写出的 20 个数字是：
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

分析

digits 数组中每个元素都是大于0的，没有前导零的问题

但是需要考虑组成的数字位数，例如，当 n = 100 时，结果集中包含11,13这样的二位数字，在按照数位填数的时候，实际上是跳过了第一位的， $\text{isNum}$ 参数必要

令 $f(i, isLimit, isNum)$ 为从左向右第 $i$ 位及以后数位的合法方案（组成的数字小于等于n）个数

$\text{i}$ 代表当前数位
$\text{isLimit}$ 表示当前数位是否会受到 n 的限制
$\text{isNum}$ 表示之前数位是否填入了数字， $\text{false}$ 表示跳过当前数位

代码

class Solution {
    char[] s;
    int[] dp;
    public int atMostNGivenDigitSet(String[] dd, int n) {
        int m = dd.length;
        char[] digits = new char[m];
        for (int i = 0; i < m; ++i) {
            digits[i] = dd[i].charAt(0);
        }
        s = Integer.toString(n).toCharArray();
        int len = s.length;
        dp = new int[len];
        Arrays.fill(dp, -1);
        return f(0, true, false, digits) - 1; // 去除 全跳过的情况
    }
    int f(int i, boolean isLimit, boolean isNum, char[] digits) {
        if (i == s.length) return 1;
        // 记忆状态
        if (!isLimit && isNum && dp[i] >= 0) return dp[i];
        int res = 0;
        if (!isNum) {
            // 跳过当前数位
            res = f(i + 1, false, false, digits);
        }
        
        for (int j = 0; j < digits.length && (isLimit ? digits[j] <= s[i] : true); ++j) {
            res += f(i + 1, isLimit && digits[j] == s[i], true, digits);
        }
        if (!isLimit && isNum) dp[i] = res;
        return res;
    }
}

📔博文图谱

提及本博文的链接

「随笔」原地哈希&&位运算相关例题