数位DP - 带49的数

迷南。 2023-09-23 17:12 131阅读 0赞

**目录**

题目来源

题目描述

输入描述

输出描述

用例

题目解析

算法源码

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

### 题目来源 ###

[20200817-数位DP-带49的数\_哔哩哔哩\_bilibili][20200817-_DP-_49_bilibili]

### 题目描述 ###

求区间 \[1,n\] 范围内包含多少带 49 的数。

一个数是带 49 的数，当且仅当它的十进制表示中存在连续的两位，其中较高位为 4，较低位为 9。

比如：49, 149, 1234987 都是带 49 的数；

而 4, 12345, 94, 999444 都不是。

### 输入描述 ###

输入一个整数 n (1 ≤ n < 2^63)。

### 输出描述 ###

输出一个整数，表示区间 \[1, n\] 范围内存在多少带 49 的数。

### 用例 ###

### 题目解析 ###

本题由于数量级太大，1 ≤ n < 2^63，因此不能用暴力枚举，只能用数位DP解决。

本题解题思路和[数位DP - 带3的数\_伏城之外的博客-CSDN博客][DP - _3_-CSDN]

类似，只是数位特征从3变为了49。

也就是说，我们需要关注两级，前一级取值4，后一级取值9，才能满足条件。因此记忆化数组f不仅需要记住某级i下含49数的个数，还需要记住前一级取值是什么，即f需要初始化为二维数组。

f\[i\]\[pre\]，i表示当前级，pre表示上一级的取值。

关于f\[i\]\[pre\]的含义，可以看下代码注释，以及debug调试理解一下，这个东西已经超出语言的描述能力，只可意会不可言传。

### Java算法源码 ###

import java.util.Scanner;
    
    public class Main {
      public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
    
        int num = sc.nextInt();
    
        String tmp = num + "";
        int level = tmp.length();
    
        // 将数字num，如500，转化为整型数组[5, 0, 0]
        int[] arr = new int[level];
        for (int i = 0; i < level; i++) {
          arr[i] = Integer.parseInt(tmp.charAt(i) + "");
        }
    
        // 数位DP的核心优化：记忆化数组f
        int[][] f = new int[level][10];
        // 统计1~num范围内不含49数的个数
        int notContain49 = dfs(0, true, f, arr, 0);
    
        // 1~num范围内所有数的个数
        int total = num + 1;
    
        // 总数 - 不含49数的个数 = 含49数的个数
        System.out.println(total - notContain49);
      }
    
      // 注意dfs统计的是不含49的数
      public static int dfs(int p, boolean limit, int[][] f, int[] arr, int pre) {
        // p代表递归树的层级，树的层级又对应数位，比如树的第0层对应百位，第1层对应十位，第2层对应个位
        if (p == arr.length) return 1;
    
        // f[p][pre] 含义看43~45行注释，此行是复用逻辑，避免重复递归
        if (!limit && f[p][pre] > 0) return f[p][pre];
    
        // limit说明当前数位是否受限，比如500的百位取值会受限，只能取0~5，如果数位取值不受限，那么可取0~9，比如百位取4，则十位可取0~9
        // max是当前数位可取的最大值
        int max = limit ? arr[p] : 9;
        // count记录当前数位下不含49的数的个数
        int count = 0;
    
        // i 是当前层级的值
        for (int i = 0; i <= max; i++) {
          // 如果当前层级取值9，且前一层级取值4，那么当前数，及后续分支都是含49的数，不需要继续递归下去了
          if (i == 9 && pre == 4) continue;
          // 否则进入下一层，即p+1层
          count += dfs(p + 1, limit && i == max, f, arr, i);
        }
    
        // 如果当前数位取值不受限，则统计的不含49的数就具有复用性
        // 缓存： 如果p-1层取值pre，那么p层所有取值中不含49的数的个数； 比如可以debug理解一下，百位取值0时，完成缓存f[p][pre]：十位(p-1)取值0
        // (pre)，那么个位(p)可以取0~9任意数，组成的数都不会含49，此时对应不含49数的个数是10个（f[p][pre]）
        // 那么下次百位取1时，十位又取0了，此时就可以不用继续尝试个位取值了，可以直接复用f[2][0]的取值
        if (!limit) f[p][pre] = count;
        return count;
      }
    }

### JavaScript算法源码 ###

/* JavaScript Node ACM模式 控制台输入获取 */
    const readline = require("readline");
    
    const rl = readline.createInterface({
      input: process.stdin,
      output: process.stdout,
    });
    
    rl.on("line", (line) => {
      console.log(digitSearch(line));
    });
    
    function digitSearch(num) {
      const arr = num.split("").map(Number);
      const f = new Array(arr.length).fill(0).map(() => new Array(10));
    
      return num - 0 + 1 - dfs(0, true, f, arr, 0);
    }
    
    // 注意dfs统计的是不含49的数
    function dfs(p, limit, f, arr, pre) {
      // p代表递归树的层级，树的层级又对应数位，比如树的第0层对应百位，第1层对应十位，第2层对应个位
      if (p === arr.length) return 1;
    
      // f[p][pre] 含义看43~45行注释，此行是复用逻辑，避免重复递归
      if (!limit && f[p][pre]) return f[p][pre];
    
      // limit说明当前数位是否受限，比如500的百位取值会受限，只能取0~5，如果数位取值不受限，那么可取0~9，比如百位取4，则十位可取0~9
      // max是当前数位可取的最大值
      const max = limit ? arr[p] : 9;
    
      // count记录当前数位下不含49的数的个数
      let count = 0;
    
      // i 是当前数位的值
      for (let i = 0; i <= max; i++) {
        // 如果当前数位取值9，且前一数位取值4，那么当前数，及后续分支都是含49的数，不需要继续递归下去了
        if (i === 9 && pre === 4) continue;
        // 否则进入下一层，即p+1层
        count += dfs(p + 1, limit && i === max, f, arr, i);
      }
    
      // 如果当前数位取值不受限，则统计的不含49的数就具有复用性
      // 缓存： 如果p-1层取值pre，那么p层所有取值中不含49的数的个数； 比如可以debug理解一下，百位取值0时，完成缓存f[p][pre]：十位(p-1)取值0 (pre)，那么个位(p)可以取0~9任意数，组成的数都不会含49，此时对应不含49数的个数是10个（f[p][pre]）
      // 那么下次百位取1时，十位又取0了，此时就可以不用继续尝试个位取值了，可以直接复用f[2][0]的取值
      if (!limit) f[p][pre] = count;
    
      return count;
    }

### Python算法源码 ###

# 输入获取
    num = input()
    
    
    # 算法入口
    # 注意dfs统计的是不含49的数
    def dfs(p, limit, f, arr, pre):
        # p代表递归树的层级，树的层级又对应数位，比如树的第0层对应百位，第1层对应十位，第2层对应个位
        if p == len(arr):
            return 1
    
        # f[p][pre] 含义看43~45行注释，此行是复用逻辑，避免重复递归
        if not limit and f[p][pre] > 0:
            return f[p][pre]
    
        # limit说明当前数位是否受限，比如500的百位取值会受限，只能取0~5，如果数位取值不受限，那么可取0~9，比如百位取4，则十位可取0~9
        # maxV是当前数位可取的最大值
        maxV = arr[p] if limit else 9
    
        # count记录当前数位下不含49的数的个数
        count = 0
    
        # i 是当前层级的值
        for i in range(maxV + 1):
            # 如果当前层级取值9，且前一层级取值4，那么当前数，及后续分支都是含49的数，不需要继续递归下去了
            if i == 9 and pre == 4:
                continue
            # 否则进入下一层，即p+1层
            count += dfs(p + 1, limit and i == maxV, f, arr, i)
    
        # 如果当前数位取值不受限，则统计的不含49的数就具有复用性
        if not limit:
            # 缓存： 如果p-1层取值pre，那么p层所有取值中不含49的数的个数； 比如可以debug理解一下，百位取值0时，完成缓存f[p][pre]：十位(p-1)取值0
            # (pre)，那么个位(p)可以取0~9任意数，组成的数都不会含49，此时对应不含49数的个数是10个（f[p][pre]）
            # 那么下次百位取1时，十位又取0了，此时就可以不用继续尝试个位取值了，可以直接复用f[2][0]的取值
            f[p][pre] = count
    
        return count
    
    
    # 算法调用
    arr = list(map(int, list(num)))  # 将数字num，如500，转化为整型数组[5, 0, 0]
    
    f = [[0] * 10 for _ in range(len(num))]  # 数位DP的核心优化：记忆化数组f
    notContain49 = dfs(0, True, f, arr, 0)
    
    total = int(num) + 1  # 统计1~num范围内不含49数的个数
    print(total - notContain49)  # 总数 - 不含49数的个数 = 含49数的个数

[20200817-_DP-_49_bilibili]: https://www.bilibili.com/video/BV1ip4y1v7zw?p=2&vd_source=b5105a99a0628dd906e154263279c518
[DP - _3_-CSDN]: https://blog.csdn.net/qfc_128220/article/details/128128007