数位 DP 模板 V1.0
902. 最大为 N 的数字组合
class Solution {
String strN;
String[] digits;
int[] memo;
public int atMostNGivenDigitSet(String[] digits, int n) {
this.strN = n + "";
this.digits = digits;
memo = new int[strN.length()];
Arrays.fill(memo, -1);
return dfs(0, true, false);
}
private int dfs(int i, boolean isLimit, boolean isNum){
if (i == strN.length()){
return isNum ? 1 : 0;
}
// 不受如何约束的条件下
if (!isLimit && isNum && memo[i] > 0){
return memo[i];
}
int res = 0;
if (!isNum){
res = dfs(i + 1, false, false);
}
char up = isLimit ? strN.charAt(i) : '9';
for (String d : digits){
if (d.charAt(0) > up){
break;
}
res += dfs(i + 1, isLimit && d.charAt(0) == up, true);
}
// 不受如何约束的条件下
if (!isLimit && isNum){
memo[i] = res;
}
return res;
}
}为什么只能在不受任何条件的情况下进行记忆化？
答：当在收到限制的情况下进行记忆化，计算的结果只有在满足相同限制下才是可用的，其他条件则并不通用。只有在不受限制的情况下，才是一个真正可复用的子问题。
数位 DP 模板 V2.0
模板 V1.0 只能处理 [0, n] 范围内的情况，对于同时有上下界的情况就需要计算两次，V2.0 模板可以一次处理具有上下界限制的情况。核心参数如下：
i：表示当前处理的数位索引；
isLimitLow：表示是否还受到起始数字 low 的约束；
isLimitHigh：表示是否受到终止数字 high 的约束。
其余条件根据题目意思进行约束即可。
2999. 统计强大整数的数目
class Solution {
char[] low;
char[] high;
long[] memo;
int limit;
char[] s;
public long numberOfPowerfulInt(long start, long finish, int limit, String s) {
this.limit = limit;
this.s = s.toCharArray();
// 上界数字
this.high = Long.toString(finish).toCharArray();
// 下届数字补齐前导零
String lowStr = Long.toString(start);
lowStr = "0".repeat(high.length - lowStr.length()) + lowStr;
this.low = lowStr.toCharArray();
// 记忆化搜索
this.memo = new long[high.length];
Arrays.fill(memo, -1);
return dfs(0, true, true);
}
public long dfs(int i, boolean isLimitLow, boolean isLimitHigh) {
if (i == high.length) {
return 1;
}
if (!isLimitLow && !isLimitHigh && memo[i] != -1) {
return memo[i];
}
// 第 i 个数位可以枚举的范围 [lo, hi]
// 如果有其他限制，应当在下面的 for 循环中做限制，不能修改 lo 或 hi
int lo = isLimitLow ? low[i] - '0' : 0;
int hi = isLimitHigh ? high[i] - '0' : 9;
long res = 0;
if (i < high.length - s.length) {
// 枚举当前数位填什么，此时受到 limit 的限制
for (int d = lo; d <= Math.min(hi, limit); d++) {
res += dfs(i + 1, isLimitLow && d == lo, isLimitHigh && d == hi);
}
} else { // 此时需要满足后缀为 s，只能填 s 中对应的字符
int d = s[i - (high.length - s.length)] - '0';
if (lo <= d && d <= Math.min(hi, limit)) {
res += dfs(i + 1, isLimitLow && d == lo, isLimitHigh && d == hi);
}
}
// 不受如何约束的条件下，才进行记忆化
if (!isLimitLow && !isLimitHigh) {
memo[i] = res;
}
return res;
}
}2719. 统计整数数目
class Solution {
int MOD = 1_000_000_007;
int minSum;
int maxSum;
char[] num1;
char[] num2;
int[][] memo;
public int count(String num1, String num2, int min_sum, int max_sum) {
this.minSum = min_sum;
this.maxSum = max_sum;
int n = num2.length();
// 上界数字
this.num2 = num2.toCharArray();
// 下界数字，补齐前导零
this.num1 = ("0".repeat(n - num1.length()) + num1).toCharArray();
memo = new int[n][Math.min(9 * n, max_sum) + 1];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
// 递归入口（数字的第一位）同时受到上下界的影响
return dfs(0, 0, true, true) % MOD;
}
private int dfs(int i, int sum, boolean limitLow, boolean limitHigh) {
if (sum > maxSum) {
return 0;
}
if (i == num2.length) {
return sum >= minSum ? 1 : 0;
}
if (!limitLow && !limitHigh && memo[i][sum] != -1) {
return memo[i][sum];
}
int lo = limitLow ? num1[i] - '0' : 0; // 下界
int hi = limitHigh ? num2[i] - '0' : 9; // 上界
int res = 0;
for (int d = lo; d <= hi; d++) {
res = (res + dfs(i + 1, sum + d, limitLow && d == lo, limitHigh && d == hi)) % MOD;
}
// 不受如何约束的条件下，才进行记忆化
if (!limitLow && !limitHigh) {
memo[i][sum] = res;
}
return res;
}
}2843. 统计对称整数的数目
给你两个正整数 low 和 high 。
对于一个由 2 * n 位数字组成的整数 x ，如果其前 n 位数字之和与后 n 位数字之和相等，则认为这个数字是一个对称整数。
返回在 [low, high] 范围内的 对称整数的数目 。
状态定义：dfs(i,start,diff,isLimitLow,isLimitHigh) 表示构造第 i 位及其之后数位的合法方案数。
class Solution {
char[] low, high;
int n, diffLH;
int[][][] memo;
public int countSymmetricIntegers(int low, int high) {
this.low = String.valueOf(low).toCharArray();
this.high = String.valueOf(high).toCharArray();
this.n = this.high.length;
this.diffLH = this.n - this.low.length;
// dfs 中的 start <= diffLh，左半元素和 <= floor(n/2) * 9
this.memo = new int[n][diffLH + 1][this.n / 2 * 9 + 1];
for (int[][] mat : memo) {
for (int[] row : mat) {
Arrays.fill(row, -1);
}
}
return dfs(0, -1, 0, true, true);
}
public int dfs(int i, int start, int diff, boolean isLimitLow, boolean isLimitHigh) {
if (diff < 0) {
return 0;
}
if (i == n) {
return diff == 0 ? 1 : 0;
}
if (start != -1 && !isLimitHigh && !isLimitLow && memo[i][start][diff] != -1) {
return memo[i][start][diff];
}
int lo = isLimitLow && i >= diffLH ? low[i - diffLH] - '0' : 0;
int hi = isLimitHigh ? high[i] - '0' : 9;
// 如果前面没有填数字，剩余数位个数是奇数，则当前数位不能填数字
if (start < 0 && (n - i) % 2 == 1) {
// 如果必须填数字（lo > 0），不合法，直接返回 0
return lo > 0 ? 0 : dfs(i + 1, start, diff, true, false);
}
int res = 0;
// 判断当前数位是否在左半
boolean isLeft = start < 0 || i < (n + start) / 2;
for (int d = lo; d <= hi; d++) {
res += dfs(
i + 1,
start < 0 && d > 0 ? i : start, // 记录第一个填数字的位置
diff + (isLeft ? d : -d), // 左半 +，右半 -
isLimitLow && d == lo,
isLimitHigh && d == hi);
}
// 记忆化
if (start != -1 && !isLimitHigh && !isLimitLow) {
memo[i][start][diff] = res;
}
return res;
}
}
.png)