蓝桥杯每日一题-----数位dp练习

题目

链接

参考代码

写了两个，一个是很久以前写的，一个是最近刚写的，很久以前写的时候还不会数位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;
}
}