数位DP - 带49的数

目录

题目来源

题目描述

输入描述

输出描述

用例

题目解析

算法源码

---

题目来源

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博客

类似，只是数位特征从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数的个数