数位DP - 带3的数

雨点打透心脏的1/2处 2023-09-23 17:09 75阅读 0赞

**目录**

题目来源

题目描述

输入描述

输出描述

用例

题目解析

算法源码

--------------------

### 题目来源 ###

[数位DP\_哔哩哔哩\_bilibili][DP_bilibili]

### 题目描述 ###

求区间\[L,R\]范围内有多少带3的数。

所谓带3的数就是这个数的十进制表示中存在至少一位为3。

比如3, 123, 3333,都是带3的数，如12, 456, 1000都是不带3的数

### 输入描述 ###

输入一行包含两个整数 L,R（1 ≤ L ≤ R ≤ 10^12）。

### 输出描述 ###

输出一个整数，表示区间\[L,R\]范围内带3的数的个数。

### 用例 ###

### 题目解析 ###

本题最容易想到的思路就是暴力枚举，从L枚举到R，统计其中含有3的枚举数。但是这种方式是O(n)时间复杂度，对于数量级1 ≤ L ≤ R ≤ 10^12来说，肯定会超时。

本题可以使用数位DP解决。[数位 DP - OI Wiki (oi-wiki.org)][DP - OI Wiki _oi-wiki.org]

![87ab7028cd30467892c6d5740336a735.png][]

再学习数位DP之前，我们需要学习数位搜索，或者数位枚举，这是一种不同于数学枚举的枚举方式。

比如，我们现在需要枚举出234内所有的数，如果是数学枚举，则代码如下：

JS：

for(let i=0; i<=234; i++) {
 	console.log(i)
 }

Python：

for i in range(235):
        print(i)

Java：

public class Main {
 public static void main(String[] args) {
 for (int i = 0; i <= 234; i++) {
 System.out.println(i);
 }
 }
 }

如果是数位搜索的话，则要复杂得多，首先我们需要将234数字转为字符串，那么得到数位关系如下：

![ab2f1aae3e7d42dd9d346fcae6cea565.png][]

*  第0位（百位）可选数为：0,1,2
 *  第1位（十位）可选数取决于第0位

1.  如果第0位的数选择0，1，则第1位可选数可以是0~9
2.  如果第0位的数选择2，则第1位可选数只能是0~3

> 如果第0位选择2，第1位选择4，那么形成的最小数为24000，那么就超过了23456；
> 
> 如果第0为选择1，第1为选择9，那么形成的最大数为19999，那么也不会超过23456；

同理可得：

*  如果第0位选取2，第1位选取3，则第2位可选数只能是0~4

图示如下：

![7ebb57d3adfc4987b8094307f02f67e9.png][] 如上图红色范围，我们称为limit，即受到上界约束的范围。

比如第0位，我们只能在0~2中选择，因为原始值234的百位最大就是2，因此被上界被约束了。

如果第0位选取了0或1，则第1位的数选择就不受约束了，可以选取0~9任意数。

如果第0位选取了2，则第1位的数选择又受到约束了，只能在0~3中选取，因为原始值百位取2时，十位最高取3。

从上图树形结构来看，我们可以借助dfs来枚举出所有情况

JS：

Python：

def dfs(level, limit, s, path):
        if level == len(s):
            print("".join(map(str, path)))
            return
    
        # 如果是约束范围，即limit为true，则当前位只能取0~str[level]，如果不是约束范围，则当前可以取0~9
        maxV = s[level] if limit else 9
    
        for i in range(maxV + 1):
            path.append(i)
            # 判断下一位取值是否为约束范围：当前位取值为约束范围，即limit为true，且当前位取值为max
            dfs(level + 1, limit and i == maxV, s, path)
            path.pop()
    
    
    def digitSearch(num):
        s = list(map(int, list(str(num))))
        dfs(0, True, s, [])
    
    
    digitSearch(234)

Java：

import java.util.Arrays;
 import java.util.LinkedList;
 
 public class Main {
 public static void main(String[] args) {
 digitSearch(234);
 }
 
 public static void digitSearch(int num) {
 Integer[] arr =
 Arrays.stream((num + "").split("")).map(Integer::parseInt).toArray(Integer[]::new);
 
 dfs(0, true, arr, new LinkedList<>());
 }
 
 public static void dfs(int level, boolean limit, Integer[] arr, LinkedList<Integer> path) {
 if (level == arr.length) {
 StringBuilder sb = new StringBuilder();
 for (Integer val : path) sb.append(val);
 System.out.println(sb);
 return;
 }
 
 // 如果是约束范围，即limit为true，则当前位只能取0~str[level]，如果不是约束范围，则当前可以取0~9
 int max = limit ? arr[level] : 9;
 
 for (int i = 0; i <= max; i++) {
 path.add(i);
 // 判断下一位取值是否为约束范围：当前位取值为约束范围，即limit为true，且当前位取值为max
 dfs(level + 1, limit && i == max, arr, path);
 path.removeLast();
 }
 }
 }

以上就是数位枚举的实现。可以看出数位枚举也属于暴力法。

但是，数位枚举是基于数位，因此我们可以更好地基于数位的特征去做一些事。

比如，比如找135内所有带3的数，此时基于数学枚举，就需要枚举0~135个数，才能找到所有带3的数：

*  3
 *  13
 *  23
 *  30，31，32，33，34，35，36，37，38，39
 *  43
 *  53
 *  63
 *  73
 *  83
 *  93
 *  103
 *  113
 *  123
 *  130,131,132,133,134,135

但是基于数位枚举，我们可以做到一些优化：

![7c821d3831204cf1bc9023836b663b08.png][]

如果当前位枚举数为3，则后面位就不需要枚举了，因为肯定含3了，相当于给dfs做了剪枝优化。

但是，我们需要注意两种情况，如上图画圈的3：

如果枚举到的数位3（绿色3），不是上界值，则对于本题的十进制数查找来说，它可以组合出Math.pow(10, str.length - level - 1)个含3数，比如：str.length=3，当前level=1（从0开始），则可以组合出10^1个。

如果枚举到的数位3（红色3），是上界值，则可以组合str.slice(level+1)，比如str.slice(2)，即'135'.slice(2) = '5'，但是需要注意，这里要+1，因为第0位取1，第1位取3时，可以组合13**0**，131，132，133，134，135，有6个数，因为包含了0。

因此最终统计含3数个数的代码如下：

JS：

Python：

import math
    
    
    def dfs(level, limit, s):
        if level == len(s):
            return 0
    
        maxV = int(s[level]) if limit else 9
        count = 0
    
        for i in range(maxV + 1):
            # 枚举到3，则后面位就不需要枚举了，必然含3
            if i == 3:
                # 统计含3数的个数
                if limit and i == maxV:  # 如果当前枚举3是上界值
                    count += int("".join(s[level + 1:])) + 1  # 从0计数，因此要加1
                else:
                    count += int(math.pow(10, len(s) - level - 1))
            else:
                count += dfs(level + 1, limit and i == maxV, s)
    
        return count
    
    
    def digitSearch(num):
        s = str(num)
        count = dfs(0, True, s)
        print(count)
    
    
    digitSearch(135)

Java：

import java.util.Arrays;
 
 public class Main {
 public static void main(String[] args) {
 digitSearch(135);
 }
 
 public static void digitSearch(int num) {
 Integer[] arr =
 Arrays.stream((num + "").split("")).map(Integer::parseInt).toArray(Integer[]::new);
 
 int count = dfs(0, true, arr);
 
 System.out.println(count);
 }
 
 public static int dfs(int level, boolean limit, Integer[] arr) {
 if (level == arr.length) {
 return 0;
 }
 
 // 如果是约束范围，即limit为true，则当前位只能取0~str[level]，如果不是约束范围，则当前可以取0~9
 int max = limit ? arr[level] : 9;
 
 int count = 0;
 
 for (int i = 0; i <= max; i++) {
 // 枚举到3，则后面位就不需要枚举了，必然含3
 if (i == 3) {
 // 统计含3数的个数
 if (limit && i == max) { // 如果当前枚举3是上界值
 Integer[] tmp = Arrays.copyOfRange(arr, level + 1, arr.length);
 StringBuilder sb = new StringBuilder();
 for (Integer val : tmp) sb.append(val);
 count += Integer.parseInt(sb.toString()) + 1; // 从0计数，因此要加1
 } else {
 count += Math.pow(10, arr.length - level - 1);
 }
 } else {
 count += dfs(level + 1, limit && i == max, arr);
 }
 }
 
 return count;
 }
 }

我们可以发现统计带3的数的个数的逻辑有些复杂，因此我们可以转换思维，统计不带3的数的个数，之后用总数 - 不带3的数的个数 = 带3的数的个数

JS：

Python：

import math
    
    
    def dfs(level, limit, s):
        if level == len(s):
            return 1  # 能走到最后的肯定是不带3的数，因此算统计到1个带3的数，返回1个
    
        maxV = int(s[level]) if limit else 9
        count = 0
    
        for i in range(maxV + 1):
            #  只统计不带3的数的个数
            if i != 3:
                count += dfs(level + 1, limit and i == maxV, s)
    
        return count
    
    
    def digitSearch(num):
        s = str(num)
        count = num + 1 - dfs(0, True, s)  # 总数 - 不带3数的个数 = 带3数的个数
        print(count)
    
    
    digitSearch(135)

Java：

import java.util.Arrays;
 
 public class Main {
 public static void main(String[] args) {
 digitSearch(135);
 }
 
 public static void digitSearch(int num) {
 Integer[] arr =
 Arrays.stream((num + "").split("")).map(Integer::parseInt).toArray(Integer[]::new);
 
 int count = num + 1 - dfs(0, true, arr); // 总数 - 不带3数的个数 = 带3数的个数
 
 System.out.println(count);
 }
 
 public static int dfs(int level, boolean limit, Integer[] arr) {
 if (level == arr.length) {
 return 1; // 能走到最后的肯定是不带3的数，因此算统计到1个带3的数，返回1个
 }
 
 // 如果是约束范围，即limit为true，则当前位只能取0~str[level]，如果不是约束范围，则当前可以取0~9
 int max = limit ? arr[level] : 9;
 
 int count = 0;
 
 for (int i = 0; i <= max; i++) {
 // 只统计不带3的数的个数
 if (i != 3) {
 count += dfs(level + 1, limit && i == max, arr);
 }
 }
 
 return count;
 }
 }

但是上面这种剪枝优化，对于数量级1 ≤ L ≤ R ≤ 10^12来说，只能算杯水车薪。

数位DP问题，一个最最最重要的优化点就是：

> 如下图中，画圈的两个十位，由他们组成的数中含有3的数的个数是相同的。
> 
> 比如：
> 
> 000、001、002、003、004、005、006、007、008、009
> 
> 090、091、092、093、094、095、096、097、098、099
> 
> 可以发现，它们的共同特点是，百位、十位都不含3，唯一可能含3的就是个位，但是它们的个位取值范围都是相同的，即0~9。因此，最终它们的含3数个数相同。

![f528779b8451416f92fb4d628b239537.png][]

因此，我们在统计出00x的含3数个数后，可以将结果缓存起来，当统计09x时，直接取缓存值即可。这样就避免了大量的深度递归操作。

我们可以定义一个数组f，f\[i\]表示第i位含3数的个数。比如f\[1\]表示第1位，即十位，含3数的个数，比如00x含3数个数，09x含3数个数。

那么可以复用f\[i\]的条件是什么呢？

![754325529cd241cd9d36010b8146bb2f.png][]

如上图画圈的两个十位，它们是否可以复用f\[1\]的统计结果吗？

答案是不可以。

> 030、031、032、033、034、035、036、037、038、039
> 
> 130、131、132、133、134、135

可以发现03x和13x的含3数个数，都不同于00x和09x。

那么到底该如何排除掉这些情况呢？

首先，如果某级取值受到上界约束，那么此时f\[i\]，i代表当前级，就无法复用，比如f\[0\]

![1c926f07f7b84310a32effe536a15370.png][]

明显的0\*\*和1\*\*下的含3数的个数是不同的。因为1\*\*的十位和个位的取值都会受到约束。而0\*\*的十位和个位取值不会受到约束。

因此，首先要排除掉对处于约束范围的级的f\[i\]的统计，即如果当前level对应的limit为true，则不需要缓存结果。

另外，如果某级取值不受上界约束，比如03\*，但是由于含有3，个位无论取何值都会含3，因此03\*和其他如01\*、02\*、04\*、....、09\*的含3数个数不同。

由于，我们采用的是深度递归，因此，必然是先统计0\*\*，然后遍历所有01\*，记忆到f\[1\]中，然后遍历02\*，从缓存结果f\[1\]中直接获取结果，之后遍历03\*，发现含3，因此跳过，之后遍历04\*，从f\[1\]中直接获取结果，后面同理。

因此实现代码如下，新增了三行关于f数组记忆化搜索的代码

JS：

Python：

def dfs(level, limit, s, f):
        if level == len(s):
            return 1
    
        if not limit and f[level] is not None:  # 记忆化搜索
            return f[level]
    
        maxV = int(s[level]) if limit else 9
        count = 0
    
        for i in range(maxV + 1):
            if i != 3:
                count += dfs(level + 1, limit and i == maxV, s, f)
    
        if not limit:  # 记忆化
            f[level] = count
    
        return count
    
    
    def digitSearch(num):
        s = str(num)
        f = [None]*len(s)  # f[i]表示第i位不含3的数的个数
        count = num + 1 - dfs(0, True, s, f)
        print(count)
    
    
    digitSearch(135)

Java：

import java.util.Arrays;
 
 public class Main {
 public static void main(String[] args) {
 digitSearch(135);
 }
 
 public static void digitSearch(int num) {
 Integer[] arr =
 Arrays.stream((num + "").split("")).map(Integer::parseInt).toArray(Integer[]::new);
 
 int[] f = new int[arr.length]; // f[i]表示第i位不含3的数的个数
 
 int count = num + 1 - dfs(0, true, arr, f); // 总数 - 不带3数的个数 = 带3数的个数
 
 System.out.println(count);
 }
 
 public static int dfs(int level, boolean limit, Integer[] arr, int[] f) {
 if (level == arr.length) {
 return 1; // 能走到最后的肯定是不带3的数，因此算统计到1个带3的数，返回1个
 }
 
 if (!limit && f[level] > 0) return f[level]; // 记忆化搜索
 
 // 如果是约束范围，即limit为true，则当前位只能取0~str[level]，如果不是约束范围，则当前可以取0~9
 int max = limit ? arr[level] : 9;
 
 int count = 0;
 
 for (int i = 0; i <= max; i++) {
 // 只统计不带3的数的个数
 if (i != 3) {
 count += dfs(level + 1, limit && i == max, arr, f);
 }
 }
 
 if (!limit) f[level] = count; // 记忆化
 
 return count;
 }
 }

最后，找L，R范围内的含3数的个数，即先找0~L-1范围内的含3数个数count1，再找0~R范围内的含3数的个数count2，然后用count2 - count1作为题解。

### JavaScript算法源码 ###

/* JavaScript Node ACM模式 控制台输入获取 */
 const readline = require("readline");
 
 const rl = readline.createInterface({
 input: process.stdin,
 output: process.stdout,
 });
 
 rl.on("line", (line) => {
 const [L, R] = line.split(" ").map(Number);
 
 console.log(digitSearch(R) - digitSearch(L - 1));
 });
 
 function dfs(level, limit, str, f) {
 if (level === str.length) {
 return 1;
 }
 
 if (!limit && f[level]) return f[level]; // 记忆化搜索
 
 const max = limit ? str[level] : 9;
 let count = 0;
 
 for (let i = 0; i <= max; i++) {
 if (i !== 3) {
 count += dfs(level + 1, limit && i === max, str, f);
 }
 }
 
 if (!limit) f[level] = count; // 记忆化
 
 return count;
 }
 
 function digitSearch(num) {
 const str = String(num).split("").map(Number);
 const f = new Array(str.length); // f[i]表示第i位不含3的数的个数
 return num + 1 - dfs(0, true, str, f);
 }

### Python算法源码 ###

# 数位搜索 + 记忆化存储
    def dfs(level, limit, s, f):
        if level == len(s):
            return 1
    
        if not limit and f[level] is not None:  # 记忆化搜索
            return f[level]
    
        maxV = int(s[level]) if limit else 9
        count = 0
    
        for i in range(maxV + 1):
            if i != 3:
                count += dfs(level + 1, limit and i == maxV, s, f)
    
        if not limit:  # 记忆化
            f[level] = count
    
        return count
    
    
    # 算法入口
    def digitSearch(num):
        s = str(num)
        f = [None]*len(s)  # f[i]表示第i位不含3的数的个数
        return num + 1 - dfs(0, True, s, f)
    
    
    # 输入获取
    L, R = map(int, input().split())
    print(digitSearch(R) - digitSearch(L-1))

### Java算法源码 ###

import java.util.Arrays;
 import java.util.Scanner;
 
 public class Main {
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 
 int l = sc.nextInt();
 int r = sc.nextInt();
 
 System.out.println(digitSearch(r) - digitSearch(l - 1));
 }
 
 public static int digitSearch(int num) {
 Integer[] arr =
 Arrays.stream((num + "").split("")).map(Integer::parseInt).toArray(Integer[]::new);
 
 int[] f = new int[arr.length]; // f[i]表示第i位不含3的数的个数
 
 return num + 1 - dfs(0, true, arr, f);
 }
 
 public static int dfs(int level, boolean limit, Integer[] arr, int[] f) {
 if (level == arr.length) {
 return 1; // 能走到最后的肯定是不带3的数，因此算统计到1个带3的数，返回1个
 }
 
 if (!limit && f[level] > 0) return f[level]; // 记忆化搜索
 
 // 如果是约束范围，即limit为true，则当前位只能取0~str[level]，如果不是约束范围，则当前可以取0~9
 int max = limit ? arr[level] : 9;
 
 int count = 0;
 
 for (int i = 0; i <= max; i++) {
 // 只统计不带3的数的个数
 if (i != 3) {
 count += dfs(level + 1, limit && i == max, arr, f);
 }
 }
 
 if (!limit) f[level] = count; // 记忆化
 
 return count;
 }
 }

[DP_bilibili]: https://www.bilibili.com/video/BV1ip4y1v7zw/?spm_id_from=333.1007.top_right_bar_window_default_collection.content.click
[DP - OI Wiki _oi-wiki.org]: https://oi-wiki.org/dp/number/
[87ab7028cd30467892c6d5740336a735.png]: https://img-blog.csdnimg.cn/87ab7028cd30467892c6d5740336a735.png
[ab2f1aae3e7d42dd9d346fcae6cea565.png]: https://img-blog.csdnimg.cn/ab2f1aae3e7d42dd9d346fcae6cea565.png
[7ebb57d3adfc4987b8094307f02f67e9.png]: https://img-blog.csdnimg.cn/7ebb57d3adfc4987b8094307f02f67e9.png
[7c821d3831204cf1bc9023836b663b08.png]: https://img-blog.csdnimg.cn/7c821d3831204cf1bc9023836b663b08.png
[f528779b8451416f92fb4d628b239537.png]: https://img-blog.csdnimg.cn/f528779b8451416f92fb4d628b239537.png
[754325529cd241cd9d36010b8146bb2f.png]: https://img-blog.csdnimg.cn/754325529cd241cd9d36010b8146bb2f.png
[1c926f07f7b84310a32effe536a15370.png]: https://img-blog.csdnimg.cn/1c926f07f7b84310a32effe536a15370.png