使用数位动态规划算法生成包含数字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表示上一级的取值。

算法源码

/* 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);// f[i][pre] 表示 第i位，且第i-1位值为pre 的 数中， 不含49的数的个数const f = new Array(arr.length).fill(0).map(() => new Array(10));return num - 0 + 1 - dfs(0, true, f, arr, 0);
}function dfs(p, limit, f, arr, pre) {if (p === arr.length) return 1;if (!limit && f[p][pre]) return f[p][pre];const max = limit ? arr[p] : 9;let count = 0;for (let i = 0; i <= max; i++) {if (i === 9 && pre === 4) continue;count += dfs(p + 1, limit && i === max, f, arr, i);}if (!limit) f[p][pre] = count;return count;
}