动态规划——数位DP经典题目

数位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 stubif(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 stubfor (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++) {//注意，这里可以包含0for (int m = 0; m < 10; m++) {if(Math.abs(m-j) <= k) {f[i][j] += f[i-1][m];}}}}
}
}

第二个板子

1. 求区间[L,R]内符合条件的数字，转换为求区间[0,L-1]与[0,R]内符合条件的数字个数，答案就是这两个做差。
2. 在遍历数字的时候，先遍历数字的位数，假设我要求[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表示当前位数可以填的数字上界。

3. 接下来处理一下前导零，如果前导零的存在不会影响结果，那么不需要处理，否则就要处理一下前导零。比如求包含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的使用更灵活一点，他是根据题目的要求来使用的。

4. 这里主要讲记忆化递归。因为这一个板子用的是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，明显此时的状态$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 stubint 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 stubif(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 stublong 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 stubtot=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 stubif (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);//该位填0for(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 syssys.setrecursionlimit(10000)dp = [[[[-1 for _ in range(2)] for __ in range(15)] for ___ in range(10)] for ____ in range(15)]nums = [0] * 15temp = [0] * 15tot = 0def dfs(cnt, limit, zeros, k, num):if cnt == 0:return numif limit == 0 and dp[cnt][k][num][zeros] != -1:return dp[cnt][k][num][zeros]up = nums[cnt] if limit else 9st = 1 if zeros else 0res = 0if 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] = resreturn resdef solve(n, k):nonlocal tot, numstot = 0while n > 0:tot += 1nums[tot] = n % 10n = n // 10return 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数组存的是当前的位数，以及遍历到当前位数我已经选了几个非零数字。

$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 stublong m = n;int cnt = 0;while(m > 0) {//0001a[++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数组存的是当前的位数，以及遍历到当前位数的乘积，已经此时是否存在前导零。

$dp[cnt][sum][zeros]$表示当前遍历到了第cnt位，并且我已经选择了sum个非零数字，如果zeros=0，表示不存在前导零，如果zeros=1表示存在前导零。

情况2：记录贴上界的状况。那么dp数组存的是当前的位数，遍历到当前位数的乘积，此时是否存在前导零，此时是否贴上界。

$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 stublong 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 stubif(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 syssys.setrecursionlimit(10000)dp = {}a = [0] * 20global mdef dfs(cnt, product, limit, zeros):if product > m:product = m + 1if cnt == 0:return 1 if product <= m else 0if limit == 0 and cnt in dp and product in dp[cnt] and zeros in dp[cnt][product]:return dp[cnt][product][zeros]res = 0up = a[cnt] if limit else 9for i in range(0, up + 1):new_product = product if (zeros and i == 0) else product * inew_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] = resreturn resdef solve(n):cnt = 0while n > 0:cnt += 1a[cnt] = n % 10n = n // 10return dfs(cnt, 1, True, True) - 1n, 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 stublong 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 stubif(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 syssys.setrecursionlimit(10000)dp = {}a = [0] * 20global mdef dfs(cnt, product, limit, zeros):if product > m:product = m + 1if cnt == 0:return 1 if product <= m else 0key = (cnt, product, zeros, limit)if key in dp:return dp[key]res = 0up = a[cnt] if limit else 9for i in range(0, up + 1):new_product = product * i if (not zeros or i != 0) else productnew_limit = limit and (i == up)new_zeros = zeros and (i == 0)res += dfs(cnt - 1, new_product, new_limit, new_zeros)dp[key] = resreturn resdef solve(n):cnt = 0while n > 0:cnt += 1a[cnt] = n % 10n = n // 10return dfs(cnt, 1, 1, 1) - 1n, 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取模的结果。

$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 stubint 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 stubif(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个数字，以及当前数字是否以及满足要求。

$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) {//0001a[++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;
}
}