数位dp
前言
今天浅谈一下数位dp的板子，我最初接触到数位dp的时候，感觉数位dp老难了，一直不敢写，最近重新看了一些数位dp，发现没有想象中那么难，把板子搞会了，变通也会变的灵活的多！
引入
以一道例题作为数位dp的引入，题目如下，链接
数据范围为1e9，一般的算法很难把这道题拿下，类似求在一段区间范围内，满足某些条件的数字的个数，并且数据范围很大时就会联想到数位dp算法。
第一个板子
我遇到的数位dp板子有三个，第一个来源于y总的讲解，附上链接和这道题的代码，y总的讲解逻辑清晰，想学习可以直接看视频。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int[][] f = new int[11][10];
static int k;
public static void main(String[] args) throws IOException {
StreamTokenizer sc=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
sc.nextToken();
//Scanner scanner = new Scanner(System.in);
int t = (int)sc.nval;
while(t> 0) {
t--;
sc.nextToken();
k = (int)sc.nval;
sc.nextToken();
int l = (int)sc.nval;
sc.nextToken();
int r = (int)sc.nval;
//int l = scanner.nextInt();
//int r = scanner.nextInt();
for (int i = 0; i < 11; i++) {
Arrays.fill(f[i], 0);
}
init();
System.out.println(dp(r) - dp(l - 1));
//dp(r);
}
return;
}
private static int dp(int num) {
// TODO Auto-generated method stub
if(num == 0) {
return 0;
}
int res = 0;
int last = 0;//上一个位数的数字
int[] nu = new int[12];
int n = 1;
while (num > 0 ) {
nu[n++] = num%10;
num = num / 10;
}
n--;
//System.out.println(n);
for (int i = n; i > 0; i--) {//遍历位数
int x = nu[i];
int jj;
if(i == n) {
jj = 1;
}else {
jj = 0;
}
//System.out.println(x);
//System.out.println(last);
for (; jj < x; jj++) {//遍历该位数上可以填的数字
if(Math.abs(jj - last) <= k || i == n) {
//System.out.println("mm" + i);
res += f[i][jj];
}
}
if(Math.abs(x-last) <= k || i == n) {
last = x;
//System.out.println("1111");
}else {
break;
}
if(i==1) {
res++;
}
}
//加包含前导0的，其实就是加上不是和num同位数的数字，
for (int i = 1; i < n; i++) {
for (int j = 1; j < 10; j++) {//从1开始
res += f[i][j];
}
}
//System.out.println(res);
return res;
}
private static void init() {
// TODO Auto-generated method stub
for (int i = 0; i < 10; i++) {//初始化只有一位数字的时候，一定符合要求
f[1][i] = 1;//注意i一定从0开始
}
for (int i = 2; i < 10; i++) {//初始化其它位数的数字
for (int j = 0; j < 10; j++) {//注意，这里可以包含0
for (int m = 0; m < 10; m++) {
if(Math.abs(m-j) <= k) {
f[i][j] += f[i-1][m];
}
}
}
}
}
}
第二个板子
- 求区间[L,R]内符合条件的数字，转换为求区间[0,L-1]与[0,R]内符合条件的数字个数，答案就是这两个做差。
- 在遍历数字的时候，先遍历数字的位数，假设我要求[0,R]内满足条件的数字，R的位数为cnt，在遍历cnt的时候我要注意，不能超过R，如果R是23456，那么第cnt位能够选择的数字范围是[0,2]。如果我第cnt位选择了1，在遍历cnt-1位的时候我就不需要考虑遍历数字是否越界问题，因为cnt位已经决定了后面的位数怎么选都不会比23456大。如果第cnt位选择了2，在遍历cnt-1位时我可以填的范围就变成了[0,3]，所以我需要有一个变量记录当前我前面选择的数字是否是贴上界的，令这个变量为limit，如果limit=1，当前位数可以选择的数字上界是a[cnt]，否则就是9，其中数组a是把23456拆分的结果，拆分代码如下
int cnt = 0;
while(n > 0) {
a[++cnt] = (int) (n%10);
n/=10;
}
根据上述分析，会有如下代码，
int up = limit==1?a[cnt]:9;//求当前位数最大能够填的数字
limit&(i==up?1:0)//下一个limit是否还等于1，i表示当前位数填的数字，如果填了最大的那个数，且当前的limit是1，则填下一位数时能够填的最大数字也是受约束的
up表示当前位数可以填的数字上界。
接下来处理一下前导零，如果前导零的存在不会影响结果，那么不需要处理，否则就要处理一下前导零。比如求包含2和4的数字个数就不需要处理前导0，因为他不影响结果。如果要求数字各个位数不为0
假设我要求[0,R]内满足条件的数字，R的位数为cnt，在遍历cnt的时候我要注意，在这个位置填的0就是前导0，如果我在这个位置填了0，再去遍历第cnt-1位数字时，这里填的0还是前导0.如果我第cnt位没有填0，那么我在cnt-1位填的0就不是前导0，他是有效的一个数，就像001和101一样，00里面的0都是前导0，是无效的。而101里的0是十位上的0，是有效的。我们用zeros来表示当前位的0是否是前导0，第cnt位的0肯定是前导0，如果第cnt位填了0，第cnt-1位的0才是前导0，否则就不是。所以有zeros&(i==0?1:0)//表示下一位的zeros是否是0，i表示当前位填的数字，如果当前位填了0并且当前位的zeros是1，那么下一位的zeros也是1.
前导0的使用要比上界limit的使用更灵活一点，他是根据题目的要求来使用的。
这里主要讲记忆化递归。因为这一个板子用的是dfs，而dfs可能会有超时的问题，所以就有了记忆化递归。记忆化递归要标记好当前的状态，所以用来记忆当前状态的数组也是要根据题目设定。
当题目中有多个测评样例时，进行记忆化的时候要注意不要记住在特定数下的答案。所以有下面的代码if(limit == 0) dp[cnt][last][zeros] = res;为什么要在limit=0时才进行记忆化呢？因为limit=1说明当前的数是贴上界的，而这个数是受当前这个样例影响的，比如2345这个数字，在遍历到百位数字3时，我是贴上界的，如果千位数字是2，那么此时十位数字只能选0-4，此时得到的res是从0-4递归得到的。但是如果换一个数字2377，在遍历到百位数字3时，我如果是不贴上界的，可选的数字应该是0-9，如果是贴上界的，可选的数字是0-7，明显此时的状态 d p [ 3 ] [ 3 ] [ 0 ] dp[3][3][0] dp[3][3][0]和数字2345的转移是不一样的。所以我只有不贴上界的时候，说明后面的转移都是0-9时才进行记忆。
读取记忆的时候也是同样的道理，if(limit==0&&dp[cnt][last][zeros]!=-1) { return dp[cnt][last][zeros]; }只有此时不贴上界的时候才能读取之前的记忆。
记忆化数组根据具体的题目来设定，并不是统一的，具有高度灵活性，只要解释起来没问题就可以。像小明数这道题没有记忆limit，有些情况也是可以记忆limit的。
分析题目
针对小明数而言，前导0会影响答案，为什么？题目要求相邻两数之差绝对值不超过k，如果存在前导0并且不加以判断那么会认为前导0也是有效数字，那么0后面只能填0-k，但实际前导0应该是无效数字，前面一个数字是前导0，后面可以填0~9中的任意一个数字。如果没有判断前导零，会导致结果比实际的小。
求某些数字相邻位数上的数字之差的绝对值不超过k，来想一下dfs的时候需要什么，必然要有的是当前的位数cnt和是否贴上界limit，刚刚也分析了需要判断前导零，所以有zeros。遍历到cnt位时，来判断一下当前位可以填啥，我要满足相邻位数上的数字之差的绝对值不超过k，我得知道前一个位数我填的是几，所以就有了last，指示前一个位数上填的数字。然后就没有其它的了，所以 dfs(cnt,last,zeros,limit)，接下来就直接放代码了。
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int dp[][][] = new int[20][20][2];//还要记录当前的状态是不是有前导零！！！！！！！
static int a[] = new int[20];
static int k,ans;
static int nums[] = new int[20];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
while(t-- > 0) {
for(int i = 0;i < 20;i++)
for(int j = 0;j < 20;j++)
Arrays.fill(dp[i][j],-1);
k = scanner.nextInt();
long l = scanner.nextLong();
long r = scanner.nextLong();
System.out.println(solve(r)-solve(l-1));
private static int solve(long n) {
// TODO Auto-generated method stub
int cnt = 0;
while(n > 0) {
a[++cnt] = (int) (n%10);
n/=10;
}
return dfs(cnt,1,-1,1);
}
private static int dfs(int cnt, int limit, int last,int zeros) {//前导0对答案有影响！！！！！！
// TODO Auto-generated method stub
if(cnt==0) {
return 1;
}
if(limit==0&&dp[cnt][last][zeros]!=-1) {
return dp[cnt][last][zeros];
}
int res =0;
int up = limit==1?a[cnt]:9;
for(int i = 0;i <= up;i++) {
if(Math.abs(last-i)<=k||zeros==1) {//3 1 2 0 dp[1][0]
res += dfs(cnt-1, limit&(i==up?1:0), i,zeros&(i==0?1:0));//120
}
}
if(limit == 0) dp[cnt][last][zeros] = res;
return res;
}
}
如果代码有问题，欢迎在评论区内提出来！第三个板子就不讲啦，其实就是把第二个板子的dfs变成dp，但是个人感觉没有dfs灵活，目前在用第二个板子。
例题2：数字计数
题目
参考代码
写了两个，一个是很久以前写的，一个是最近刚写的，很久以前写的时候还不会数位dp所以写了比较详细的注释，这两个代码主要是设置了不同的记忆数组，通过这两个代码可以理解记忆数组设置的灵活性。
import java.util.Scanner;
public class Main {
// 给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。
static int[] b = new int[15];
static long[][][] f = new long[15][10][15];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long n = scanner.nextLong();
long m = scanner.nextLong();
for (int i = 0; i < 15; i++) {
for (int j = 0; j < 10; j++) {
for (int j2 = 0; j2 < 15; j2++) {
f[i][j][j2] = -1;
}
}
}
for (int i = 0; i <= 9; i++) {
System.out.print((get(m, i) - get(n - 1, i)) + " ");
}
}
private static long get(long x, int target) {
// TODO Auto-generated method stub
long t = x;
int i = 0;
while (t > 0) {
b[i++] = (int) (t % 10);
t = t / 10;
}
return dfs(target, true, true, i - 1, 0);
}
// target 表示要计算的值
// e 是否贴上界
//当要判断的数的位数小于原数的位数时，就没有上界了，如果位数和原数一样，每一位的上界就是对应的原数
// first 是否是数的第一个位
// k 数的第几位 now
// t 出现的次数
private static long dfs(int target, boolean e, boolean first, int k, int t) {
// TODO Auto-generated method stub
//
long res = 0;
if (k == -1)
return t;// 如果数位考虑完，返回出现的次数
// f[k][target][t]时公用的，找这个x的时候可以用，找下一个x的时候也可以用，所以他应该具有普遍性，
// 但是当我的位数和x一样时，他有不同的边界
if ((!e) && (!first) && f[k][target][t] != -1)
return f[k][target][t];
// 判断这一位我可以最大填到哪个数
int u = e ? b[k] : 9;
// 如果是要填写首位数，那么这个数等于0的时候其实位数是减一，要单独考虑。
if (first) {
res += dfs(target, false, true, k - 1, t);
}
// 注意我已经判断了如果要给首位填数，首位数为0的情况，所以当要给首位填数时，我要从1开始，如果不是首位，那么从0开始即可
for (int i = first ? 1 : 0; i <= u; i++) {
// 贴上界是指此时的位数的上界是受此位的数的限制，最大数可能到达不了9
// 只有本位是贴上界的下一位才有贴上界的可能，比如54321，只要是第五位他的上界就是5，也就是此位最大取到5，
// 这也就是为什么在get中一开始遍历的时候e = true
// 当确定了这个数是5位的时候，如果第五位小于5，那他后面的数是不贴上界的最大值可以写到9，但如果第五位等于5
// 那下一位也是贴上界的，最大值只能取到4
// (i == u) & e 这也是它的来源
res += dfs(target, (i == u) & e, false, k - 1, (i == target) ? t + 1 : t);
}
// f[k][target][t]时公用的，找这个x的时候可以用，找下一个x的时候也可以用,所以他应该具有普遍性，
// 但是当我的位数和x一样时，他有不同的边界限制，此时他得出的值具有个性，不能给其他的x用，所以不能存在f数组中
// 这是为什么要判断是否贴上界的原因
// 当该位数为一个数的首位时，因为此时该数的实际位数是不确定的，首位为0时实际位数会减少，但我依然记录在res中，这样此时的
// (f[k][target][t] 就有两种情况一是k是首位的时候，二是k不是首位的时候，所以我们应该舍去k时首位的时候
if (!e && !first) {
f[k][target][t] = res;
}
return res;
}
}
import java.util.Arrays;
import java.util.Scanner;
public class 数字计数 {
static long dp[][][][] = new long[15][10][15][2];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long a = scanner.nextLong();
long b = scanner.nextLong();
for(int i = 0;i < 15;i++)
for(int j = 0;j < 10;j++)
for(int k = 0;k < 15;k++)
Arrays.fill(dp[i][j][k], -1);
for(int i = 0;i < 10;i++)
System.out.print(solve(b,i)-solve(a-1,i)+" ");//20 21 2 12 22 32 42 52 62 72 82 92 23 24 25 26 27 28 29
// System.out.println(solve(b, 2));//2 12 20-29(10) 32 42 52 62 72 82 92 22
}
static int nums[] = new int[15];
static int temp[] = new int[15];
static int tot = 0;
private static long solve(long n,int k) {
// TODO Auto-generated method stub
tot=0;
while(n > 0) {
nums[++tot] = (int) (n % 10);
n /= 10;
}
return dfs(tot,1,1,k,0);
}
private static long dfs(int cnt, int limit, int zeros, int k, int num) {
// TODO Auto-generated method stub
if (cnt==0) {
// for(int i = 1;i <= 2;i++) System.out.print(temp[i]);
// System.out.println( " "+ num);
return num;
}
if(limit==0&&dp[cnt][k][num][zeros]!=-1) return dp[cnt][k][num][zeros];
int up = limit==1?nums[cnt]:9;
int st = zeros==1?1:0;
long res = 0;
if(zeros==1) res+=dfs(cnt-1, (0==up?1:0)&limit, 1, k, num);//该位填0
for(int i = st;i <= up;i++) {
// temp[cnt]=i;
res+=dfs(cnt-1, (i==up?1:0)&limit, 0, k, i==k?num+1:num);
}
if(limit==0) dp[cnt][k][num][zeros]=res;
return res;
}
}
#include <iostream>
#include <cstring>
using namespace std;
long long dp[15][10][15][2];
int nums[15];
int temp[15];
int tot = 0;
long long dfs(int cnt, int limit, int zeros, int k, int num) {
if (cnt == 0) {
return num;
}
if (limit == 0 && dp[cnt][k][num][zeros] != -1) return dp[cnt][k][num][zeros];
int up = limit == 1 ? nums[cnt] : 9;
int st = zeros == 1 ? 1 : 0;
long long res = 0;
if (zeros == 1) res += dfs(cnt - 1, (0 == up ? 1 : 0) & limit, 1, k, num);
for (int i = st; i <= up; i++) {
res += dfs(cnt - 1, (i == up ? 1 : 0) & limit, 0, k, i == k ? num + 1 : num);
}
if (limit == 0) dp[cnt][k][num][zeros] = res;
return res;
}
long long solve(long long n, int k) {
tot = 0;
while (n > 0) {
nums[++tot] = n % 10;
n /= 10;
}
return dfs(tot, 1, 1, k, 0);
}
int main() {
long long a, b;
cin >> a >> b;
memset(dp, -1, sizeof(dp));
for (int i = 0; i < 10; i++) {
cout << solve(b, i) - solve(a - 1, i) << " ";
}
return 0;
}
def main():
import sys
sys.setrecursionlimit(10000)
dp = [[[[-1 for _ in range(2)] for __ in range(15)] for ___ in range(10)] for ____ in range(15)]
nums = [0] * 15
temp = [0] * 15
tot = 0
def dfs(cnt, limit, zeros, k, num):
if cnt == 0:
return num
if limit == 0 and dp[cnt][k][num][zeros] != -1:
return dp[cnt][k][num][zeros]
up = nums[cnt] if limit else 9
st = 1 if zeros else 0
res = 0
if zeros:
res += dfs(cnt-1, (1 if 0 == up else 0) & limit, 1, k, num)
for i in range(st, up+1):
res += dfs(cnt-1, (1 if i == up else 0) & limit, 0, k, num+1 if i == k else num)
if limit == 0:
dp[cnt][k][num][zeros] = res
return res
def solve(n, k):
nonlocal tot, nums
tot = 0
while n > 0:
tot += 1
nums[tot] = n % 10
n = n // 10
return dfs(tot, 1, 1, k, 0)
a, b = map(int, input().split())
results = []
for i in range(10):
results.append(str(solve(b, i) - solve(a-1, i)))
print(' '.join(results))
if __name__ == "__main__":
main()
优雅的数字
题目分析
动态规划三阶段
第一个阶段定义dp数组
（1）缩小规模。对于数位dp的规模就是数字的位数，一般从最高位开始遍历。
（2）考虑限制。数位dp的限制特别重要。
包含不超过3个非零数字。
在这一步我们就可以去规定如何写dfs了
dfs(int cnt,int limit)//首先必须要有的是，当前考虑的数字位数，是否贴上界
//这一题要求非零数字不能超过3个，那么我们需要记录当前已经出现的非零数字的个数，用sum记录，即
dfs(int cnt,int limit,int sum)
//现在来考虑前导零是否会影响结果。12符合要求，0012也是符合要求的，1234不符合要求，001234也是不符合要求的所以前导0不影响结果。
（3）定义dp数组。
根据写出来的dfs定义dp数组，主要这道题有好几个[l,r]，而对于不同的值，他的上界是不一样的，所以我们没办法同一表示贴上界时的情况是什么样子的。所以贴上界时不把他放在dp数组里，不贴上界的操作都是一样的，需要放在dp数组里面，那么dp数组存的是当前的位数，以及遍历到当前位数我已经选了几个非零数字。
d p [ c n t ] [ s u m ] dp[cnt][sum] dp[cnt][sum]表示当前遍历到了第cnt位，并且我已经选择了sum个非零数字。
第二个阶段推导状态转移方程
对于数位dp，状态转移方程直接放在写代码那步。
第三个阶段写代码
dfs(int cnt,int limit,int sum){
if(cnt==0)//表示我已经遍历完了
return 1;//找到了一个合法数字
if(limit==0&&dp[cnt][sum]!=-1)//如果当前不贴上界并且之前已经找过遍历到第cnt位并且已经选了sum个数的情况，我可以直接返回
return dp[cnt][sum];
int up=limit==1?a[cnt]:9;//如果limit=1表示贴上界，那么我这一位最大只能选到a[cnt]否则就是可以选到最大值9。如果我要找[0,num]内符合要求的数字个数，这里的a[i]存了数字num每一位上的值。
long res = 0;//统计从这一步向后走能够找到的合法数字总数
for(int i = 0;i <= up;i++){
if(i==0)//因为我们要保证非零数字的个数，所以这一位填0还是非0我要知道
res += dfs(cnt-1,(limit==1)&&(i==up)?1:0,sum)//如果limit=1并且i选取了up，那么下一个依然是贴上界的，否则就不是。因为i是0，所以sum的值不改变
else if(sum<3)//表示我还可以选择非零的数字
res += dfs(cnt-1,(limit==1)&&(i==up)?1:0,sum+1)//现在选择的是非零数字，所以sum要加1
}
if(limit==0) dp[cnt][sum]=res;//如果不贴上界，说明我可以记录下来
return res;
}
题目代码
import java.util.Arrays;
import java.util.Scanner;
public class Main{
static int dp[][]= new int[20][4];//当前数字的位数，当前非零数字的个数
static int a[] = new int[20];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
for(int i = 0;i < 18;i++) Arrays.fill(dp[i], -1);
while(t-- > 0) {
long l = scanner.nextLong();
long r = scanner.nextLong();
System.out.println(solve(r)-solve(l-1));
}
}
private static int solve(long n) {
// TODO Auto-generated method stub
long m = n;
int cnt = 0;
while(m > 0) {//0001
a[++cnt] = (int) (m%10);
m /= 10;
}
return dfs(cnt,0,1);
}
private static int dfs(int cnt, int sum, int limit) {
if(cnt==0) return 1;
if(limit==0&&dp[cnt][sum]!=-1) return dp[cnt][sum];
int res = 0;
int up = limit == 1?a[cnt]:9;
for(int i = 0;i <= up;i++) {
if(i==0) res+=dfs(cnt-1, sum, limit&(i==up?1:0));
else if(sum < 3) res += dfs(cnt-1, sum+1, limit&(i==up?1:0));
}
if(limit==0) dp[cnt][sum] = res;
return res;
}
}
小熊的困惑
题目分析
动态规划三阶段
第一个阶段定义dp数组
（1）缩小规模。对于数位dp的规模就是数字的位数，一般从最高位开始遍历。
（2）考虑限制。数位dp的限制特别重要。
每一位的乘积小于等于m的数字。
在这一步我们就可以去规定写dfs需要哪些传参
dfs(int cnt,int limit)//首先必须要有的是，当前考虑的数字位数，是否贴上界
//这一题要求每一位的乘积小于等于m，那么我们需要记录当前数字每一位的乘积，用product记录，即
dfs(int cnt,int limit,long pruduct)
//现在来考虑前导零是否会影响结果。如果m=4，那么23肯定是不符合要求的，但是023就是符合要求的了，也就是前导0会影响我的判断。而且求的是[1,n]符合要求的数字个数，我没有[l,r]-[1,l-1]这种操作，多出来的符合要求的数字我不能减掉，所以前导零会影响结果，因此我需要判断前导0。
dfs(int cnt,int limit,long pruduct,int zeros)
（3）定义dp数组。
根据写出来的dfs定义dp数组，主要这道题而对于不同的值，他的上界是一样的，我们可以记录贴上界时的情况，当然也可以只记录不贴上界时的情况。前导零需要记录。
情况1：不记录贴上界的状况。贴上界时不把他放在dp数组里，不贴上界的操作都是一样的，需要放在dp数组里面，那么dp数组存的是当前的位数，以及遍历到当前位数的乘积，已经此时是否存在前导零。
d p [ c n t ] [ s u m ] [ z e r o s ] dp[cnt][sum][zeros] dp[cnt][sum][zeros]表示当前遍历到了第cnt位，并且我已经选择了sum个非零数字，如果zeros=0，表示不存在前导零，如果zeros=1表示存在前导零。
情况2：记录贴上界的状况。那么dp数组存的是当前的位数，遍历到当前位数的乘积，此时是否存在前导零，此时是否贴上界。
d p [ c n t ] [ s u m ] [ z e r o s ] [ l i m i t ] dp[cnt][sum][zeros][limit] dp[cnt][sum][zeros][limit]表示当前遍历到了第cnt位，并且我已经选择了sum个非零数字，如果zeros=0，表示不存在前导零，如果zeros=1表示存在前导零。如果limit=0，表示不贴上界，如果limit=1表示贴上界。
第二个阶段推导状态转移方程
第三个阶段写代码
//不记录贴上界的情况
dfs(int cnt,int limit,long product,int zeros){
//if(produt>m) return 0;//这样写是错误的，后面如果遇到了0，product变成0就是符合条件的了
if(product > m) product = m+1;//已经超出m了，那么写成m+1也是一样的，这样是防止product过大，造成内存溢出
if(cnt==0){//表示我已经遍历完了
if(product<=m) return 1;//找到了一个合法数字
else return 0
}
if(limit==0&&dp[cnt][product][zeros]!=-1)
return dp[cnt][product][zeros];
int up=limit==1?a[cnt]:9;//如果limit=1表示贴上界，那么我这一位最大只能选到a[cnt]否则就是可以选到最大值9。如果我要找[0,num]内符合要求的数字个数，这里的a[i]存了数字num每一位上的值。
long res = 0;//统计从这一步向后走能够找到的合法数字总数
for(int i = 0;i <= up;i++){
if(i==0&&zeros==1)//表示这个i是前导零，那么它不是有效的数字位数，对乘积不产生影响
res += dfs(cnt-1,(limit==1)&&(i==up)?1:0,product,(zeros==1)&&i==0?1:0)
else if(i*product<=m)//表示i我可以选择
res += dfs(cnt-1,(limit==1)&&(i==up)?1:0,i*product,(zeros==1)&&i==0?1:0)
}
if(limit==0) dp[cnt][product][zeros]=res;//如果不贴上界，说明我可以记录下来
return res;
}
//记录贴上界的情况
dfs(int cnt,int limit,long product,int zeros){
//if(produt>m) return 0;//这样写是错误的，后面如果遇到了0，product变成0就是符合条件的了
if(product > m) product = m+1;//已经超出m了，那么写成m+1也是一样的，这样是防止product过大，造成内存溢出
if(cnt==0){//表示我已经遍历完了
if(product<=m) return 1;//找到了一个合法数字
else return 0
}
if(dp[cnt][product][zeros][limit]!=-1)//如果当前不贴上界并且之前已经找过遍历到第cnt位并且已经选了sum个数的情况，我可以直接返回
return dp[cnt][product][zeros][limit];
int up=limit==1?a[cnt]:9;//如果limit=1表示贴上界，那么我这一位最大只能选到a[cnt]否则就是可以选到最大值9。如果我要找[0,num]内符合要求的数字个数，这里的a[i]存了数字num每一位上的值。
long res = 0;//统计从这一步向后走能够找到的合法数字总数
for(int i = 0;i <= up;i++){
if(i==0&&zeros==1)//表示这个i是前导零，那么它不是有效的数字位数，对乘积不产生影响
res += dfs(cnt-1,(limit==1)&&(i==up)?1:0,product,(zeros==1)&&i==0?1:0)
else if(i*product<=m)//表示i我可以选择
res += dfs(cnt-1,(limit==1)&&(i==up)?1:0,i*product,(zeros==1)&&i==0?1:0)
}
dp[cnt][product][zeros][limit]=res;//如果不贴上界，说明我可以记录下来
return res;
}
题目代码
这个题的代码要注意我存乘积的那一维度，可能要开很大的空间造成空间超限，那么我选择用map代替数组，具体看代码
不记录贴上界的情况
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main{
/*
* 内存超限，zeros也会有影响
*/
static Map<Integer, Map<Long, Map<Integer, Long>>> dp= new HashMap<Integer, Map<Long,Map<Integer,Long>>>();//当前数字的位数，当前数字的乘积
static int a[] = new int[20];
static long m;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = 1;
// for(int i = 0;i < 18;i++) Arrays.fill(dp[i], -1);
while(t-- > 0) {
long n = scanner.nextLong();
m = scanner.nextLong();
System.out.println(solve(n));
}
}
private static long solve(long n) {
// TODO Auto-generated method stub
long m = n;
int cnt = 0;
while(m > 0) {
a[++cnt] = (int) (m % 10);
m /= 10;
}
return dfs(cnt,1,1,1)-1;
}
private static Long dfs(int cnt, long product, int limit,int zeros) {
// TODO Auto-generated method stub
if(product > m) product = m+1;
if(cnt == 0) {
if(product<=m) return 1l;
else return 0l;
}
if(limit == 0&&dp.get(cnt)!=null&&dp.get(cnt).get(product)!=null&&dp.get(cnt).get(product).get(zeros)!=null)
return dp.get(cnt).get(product).get(zeros);
long res = 0;
int up = limit == 1?a[cnt]:9;
for(int i = 0;i<=up;i++) {
res+= dfs(cnt-1, (zeros!=1||i!=0)?product*i:product, limit&(i==up?1:0),zeros&(i==0?1:0));//这里写法和分析不太一样，但是本质是一样的，(zeros!=1||i!=0)表示只要zeros==1且i==0，那么i就不能乘product。
}
if(limit == 0) {
if(dp.get(cnt)==null) dp.put(cnt, new HashMap());
if(dp.get(cnt).get(product)==null) dp.get(cnt).put(product, new HashMap());
dp.get(cnt).get(product).put(zeros, res);
}
return res;
}
}
#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map<int, unordered_map<long, unordered_map<int, long>>> dp;
int a[20];
long m;
long dfs(int cnt, long product, int limit, int zeros) {
if (product > m) product = m + 1;
if (cnt == 0) {
return product <= m ? 1 : 0;
}
if (limit == 0 && dp.count(cnt) && dp[cnt].count(product) && dp[cnt][product].count(zeros)) {
return dp[cnt][product][zeros];
}
long res = 0;
int up = limit ? a[cnt] : 9;
for (int i = 0; i <= up; i++) {
long new_product = (zeros && i == 0) ? product : product * i;
int new_limit = limit && (i == up);
int new_zeros = zeros && (i == 0);
res += dfs(cnt - 1, new_product, new_limit, new_zeros);
}
if (limit == 0) {
dp[cnt][product][zeros] = res;
}
return res;
}
long solve(long n) {
int cnt = 0;
while (n > 0) {
a[++cnt] = n % 10;
n /= 10;
}
return dfs(cnt, 1, 1, 1) - 1;
}
int main() {
long n;
cin >> n >> m;
cout << solve(n) << endl;
return 0;
}
def main():
import sys
sys.setrecursionlimit(10000)
dp = {}
a = [0] * 20
global m
def dfs(cnt, product, limit, zeros):
if product > m:
product = m + 1
if cnt == 0:
return 1 if product <= m else 0
if limit == 0 and cnt in dp and product in dp[cnt] and zeros in dp[cnt][product]:
return dp[cnt][product][zeros]
res = 0
up = a[cnt] if limit else 9
for i in range(0, up + 1):
new_product = product if (zeros and i == 0) else product * i
new_limit = limit and (i == up)
new_zeros = zeros and (i == 0)
res += dfs(cnt - 1, new_product, new_limit, new_zeros)
if limit == 0:
if cnt not in dp:
dp[cnt] = {}
if product not in dp[cnt]:
dp[cnt][product] = {}
dp[cnt][product][zeros] = res
return res
def solve(n):
cnt = 0
while n > 0:
cnt += 1
a[cnt] = n % 10
n = n // 10
return dfs(cnt, 1, True, True) - 1
n, m = map(int, input().split())
print(solve(n))
if __name__ == "__main__":
main()
记录贴上界的情况
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main{
/*
* 内存超限，zeros也会有影响
*/
static Map<Integer, Map<Long, Map<Integer, Map<Integer, Long>>>> dp= new HashMap<Integer, Map<Long,Map<Integer,Map<Integer, Long>>>>();//当前数字的位数，当前数字的乘积
//位数，乘积，是否是前导0，是否贴上界，符合条件的数字个数
static int a[] = new int[20];
static long m;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = 1;
// for(int i = 0;i < 18;i++) Arrays.fill(dp[i], -1);
while(t-- > 0) {
long n = scanner.nextLong();
m = scanner.nextLong();
System.out.println(solve(n));
}
}
private static long solve(long n) {
// TODO Auto-generated method stub
long m = n;
int cnt = 0;
while(m > 0) {
a[++cnt] = (int) (m % 10);
m /= 10;
}
return dfs(cnt,1,1,1)-1;
}
private static Long dfs(int cnt, long product, int limit,int zeros) {
// TODO Auto-generated method stub
if(product > m) product = m+1;
if(cnt == 0) {
if(product<=m) return 1l;
else return 0l;
}
//cnt位数对应，乘积对应，前导0对应，上界对应
if(dp.get(cnt)!=null&&dp.get(cnt).get(product)!=null&&dp.get(cnt).get(product).get(zeros)!=null&&dp.get(cnt).get(product).get(zeros).get(limit)!=null)
return dp.get(cnt).get(product).get(zeros).get(limit);
long res = 0;
int up = limit == 1?a[cnt]:9;
for(int i = 0;i<=up;i++) {
res+= dfs(cnt-1, (zeros!=1||i!=0)?product*i:product, limit&(i==up?1:0),zeros&(i==0?1:0));//这里写法和分析不太一样，但是本质是一样的，(zeros!=1||i!=0)表示只要zeros==1且i==0，那么i就不能乘product。
}
if(dp.get(cnt)==null) dp.put(cnt, new HashMap());
if(dp.get(cnt).get(product)==null) dp.get(cnt).put(product, new HashMap());
if(dp.get(cnt).get(product).get(zeros)==null)dp.get(cnt).get(product).put(zeros, new HashMap());
dp.get(cnt).get(product).get(zeros).put(limit, res);
return res;
}
}
#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map<int, unordered_map<long, unordered_map<int, unordered_map<int, long>>>> dp;
int a[20];
long m;
long dfs(int cnt, long product, int limit, int zeros) {
if (product > m) product = m + 1;
if (cnt == 0) {
return product <= m ? 1 : 0;
}
if (dp[cnt][product][zeros][limit] != 0) {
return dp[cnt][product][zeros][limit];
}
long res = 0;
int up = limit ? a[cnt] : 9;
for (int i = 0; i <= up; i++) {
long new_product = (zeros && i == 0) ? product : product * i;
int new_limit = limit && (i == up);
int new_zeros = zeros && (i == 0);
res += dfs(cnt - 1, new_product, new_limit, new_zeros);
}
dp[cnt][product][zeros][limit] = res;
return res;
}
long solve(long n) {
int cnt = 0;
while (n > 0) {
a[++cnt] = n % 10;
n /= 10;
}
return dfs(cnt, 1, 1, 1) - 1;
}
int main() {
long n;
cin >> n >> m;
cout << solve(n) << endl;
return 0;
}
def main():
import sys
sys.setrecursionlimit(10000)
dp = {}
a = [0] * 20
global m
def dfs(cnt, product, limit, zeros):
if product > m:
product = m + 1
if cnt == 0:
return 1 if product <= m else 0
key = (cnt, product, zeros, limit)
if key in dp:
return dp[key]
res = 0
up = a[cnt] if limit else 9
for i in range(0, up + 1):
new_product = product * i if (not zeros or i != 0) else product
new_limit = limit and (i == up)
new_zeros = zeros and (i == 0)
res += dfs(cnt - 1, new_product, new_limit, new_zeros)
dp[key] = res
return res
def solve(n):
cnt = 0
while n > 0:
cnt += 1
a[cnt] = n % 10
n = n // 10
return dfs(cnt, 1, 1, 1) - 1
n, m = map(int, input().split())
print(solve(n))
if __name__ == "__main__":
main()
数位魔法
题目分析
动态规划三阶段
第一个阶段定义dp数组
（1）缩小规模。对于数位dp的规模就是数字的位数，一般从最高位开始遍历。
（2）考虑限制。数位dp的限制特别重要。
各位数字之和是k的倍数。
在这一步我们就可以去规定如何写dfs了
dfs(int cnt,int limit)//首先必须要有的是，当前考虑的数字位数，是否贴上界
//这一题要求各位数字之和是k的倍数，那么我们需要记录各位数字之和对k取模的结果就可以了，用k记录，即
dfs(int cnt,int limit,int m)
//现在来考虑前导零是否会影响结果。前导0不会对累加和产生贡献，也就是k符合条件，那么0k也符合条件。所以前导零不影响结果。
（3）定义dp数组。
根据写出来的dfs定义dp数组，主要这道题而对于不同的值，他的上界是一样的，因为我只求[1,n]符合要求的数字个数，上界数字就是n。我们可以记录贴上界时的情况，当然也可以只记录不贴上界时的情况。
这里以不记录贴上界的状况为例。贴上界时不把他放在dp数组里，不贴上界的操作需要放在dp数组里面，那么dp数组存的是当前的位数，以及遍历到当前位数的各位数字之和对k取模的结果。
d p [ c n t ] [ m ] dp[cnt][m] dp[cnt][m]表示当前遍历到了第cnt位，并且各位数字之和对k取模结果用m表示。
第二个阶段推导状态转移方程
对于数位dp，状态转移方程直接放在写代码那步。
第三个阶段写代码
dfs(int cnt,int limit,int m){
if(cnt==0){//表示我已经遍历完了
if(m==0)//表示各位数字之和是k的倍数
return 1;//找到了一个合法数字
else return 0;
}
if(limit==0&&dp[cnt][m]!=-1)
return dp[cnt][m];
int up=limit==1?a[cnt]:9;//如果limit=1表示贴上界，那么我这一位最大只能选到a[cnt]否则就是可以选到最大值9。如果我要找[0,num]内符合要求的数字个数，这里的a[i]存了数字num每一位上的值。
long res = 0;//统计从这一步向后走能够找到的合法数字总数
for(int i = 0;i <= up;i++){
res += dfs(cnt-1,(limit==1)&&(i==up)?1:0,(m+i)%k)
}
if(limit==0) dp[cnt][m]=res;//如果不贴上界，说明我可以记录下来
return res;
}
题目代码
import java.util.Arrays;
import java.util.Scanner;
public class Main{
static int dp[][]= new int[2000][200];
static int a[] = new int[2000];
static int m;
static int mod = 998244353;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = 1;
for(int i = 0;i < 2000;i++) Arrays.fill(dp[i], -1);
while(t-- > 0) {
String string = scanner.next();
m = scanner.nextInt();
System.out.println(solve(string));
}
}
private static int solve(String n) {
// TODO Auto-generated method stub
int cnt = 0;
for(int i = n.length()-1;i >= 0;i--)
a[++cnt] = n.charAt(i)-'0';
return (dfs(cnt,1,0)-1+mod)%mod;
}
private static int dfs(int cnt, int limit,int k) {
// TODO Auto-generated method stub
if(cnt == 0) {
if(k==0) return 1;
else return 0;
}
if(limit == 0&&dp[cnt][k]!=-1) return dp[cnt][k];
int res = 0;
int up = limit == 1?a[cnt]:9;
for(int i = 0;i<=up;i++) {
res=(res+ dfs(cnt-1, limit&(i==up?1:0),(k+i)%m))%mod;
}
if(limit == 0) dp[cnt][k] = res;
return res;
}
}
幸运年
题目分析
动态规划三阶段
第一个阶段定义dp数组
（1）缩小规模。对于数位dp的规模就是数字的位数，一般从最高位开始遍历。
（2）考虑限制。数位dp的限制特别重要。
包含2023或者14的数字
在这一步我们就可以去规定如何写dfs了
dfs(int cnt,int limit)//首先必须要有的是，当前考虑的数字位数，是否贴上界
//这一题要求包含2023或者14，那么我们需要记录包含当前这一位在内的前四位分别是哪个数，即
dfs(int cnt,int limit,int p1,int p2,int p3,int p4)
//还需要一个变量表示当前这个数是否符合要求，比如20230011这个数符合要求，其实遍历到2023我就知道这个数一定符合要求，即
dfs(int cnt,int limit,int p1,int p2,int p3,int p4,int f)
//现在来考虑前导零是否会影响结果。2023符合要求，002023也符合要求，24不符合要求0024也不符合要求，所以前导零不会影响我的判断，不需要管。
（3）定义dp数组。
根据写出来的dfs定义dp数组，这道题而对于不同的值，他的上界是不一样的，我们只可以记录不贴上界时的情况。
贴上界时不把他放在dp数组里，不贴上界的操作需要放在dp数组里面，那么dp数组存的是当前的位数，以及遍历到这里时前4个数字，以及当前数字是否以及满足要求。
d p [ c n t ] [ p 1 ] [ p 2 ] [ p 3 ] [ p 4 ] [ f ] dp[cnt][p1][p2][p3][p4][f] dp[cnt][p1][p2][p3][p4][f]表示当前遍历到了第cnt位，遍历到这里时前4个数字分别为p1，p2，p3，p4，如果f=1，表示当前数字已经满足要求，否则就是不满足要求。
第二个阶段推导状态转移方程
对于数位dp，状态转移方程直接放在写代码那步。
第三个阶段写代码
dfs(int cnt,int limit,int p1,int p2,int p3,int p4,int f){
//先检查一下当前数字是否已经满足要求
if(p1==2&&p2==0&&p3==2&&p4==3) f=1;
if(p3==1&&p4==4) f=1;
if(cnt==0){//表示我已经遍历完了
if(f==1)
return 1;//找到了一个合法数字
else return 0;
}
if(limit==0&&dp[cnt][p1][p2][p3][p4][f]!=-1)
return dp[cnt][p1][p2][p3][p4][f];
int up=limit==1?a[cnt]:9;//如果limit=1表示贴上界，那么我这一位最大只能选到a[cnt]否则就是可以选到最大值9。如果我要找[0,num]内符合要求的数字个数，这里的a[i]存了数字num每一位上的值。
long res = 0;//统计从这一步向后走能够找到的合法数字总数
for(int i = 0;i <= up;i++){
res += dfs(cnt-1,(limit==1)&&(i==up)?1:0,p2,p3,p4,i,f);
}
if(limit==0) dp[cnt][p1][p2][p3][p4][f]=res;//如果不贴上界，说明我可以记录下来
return res;
}
题目代码
import java.util.Arrays;
import java.util.Scanner;
public class Main{
static long dp[][][][][][]= new long[20][10][10][10][10][2];//当前数字的位数，当前非零数字的个数
static int a[] = new int[20];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = 1;
for(int i = 0;i < 20;i++)
for(int j = 0;j < 10;j++)
for(int k = 0;k < 10;k++)
for(int a = 0;a < 10;a++)
for(int b = 0;b < 10;b++)
Arrays.fill(dp[i][j][k][a][b], -1);
while(t-- > 0) {
long l = scanner.nextLong();
long r = scanner.nextLong();
System.out.println(solve(r)-solve(l-1));
}
}
private static long solve(long n) {
long m = n;
int cnt = 0;
while(m > 0) {//0001
a[++cnt] = (int) (m%10);
m /= 10;
}
return dfs(cnt,0,0,0,0,1,0);
}
private static long dfs(int cnt, int p1, int p2, int p3, int p4, int limit,int f) {
if(p1==2&&p2==0&&p3==2&&p4==3) f=1;
if(p3==1&&p4==4) f = 1;
if(cnt==0) return f==1?1:0;
if(limit==0&&dp[cnt][p1][p2][p3][p4][f]!=-1) return dp[cnt][p1][p2][p3][p4][f];
long res = 0;
int up = limit == 1?a[cnt]:9;
for(int i = 0;i <= up;i++) {
res+=dfs(cnt-1, p2,p3,p4,i, limit&(i==up?1:0),f);
}
if(limit==0) dp[cnt][p1][p2][p3][p4][f] = res;
return res;
}
}