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