模板

主要包含：

感谢支持！

一定有的参数

i, lowerBound (limitLow), UpperBound (limitHigh)
lowerBound, UpperBound在函数中一般不变化
前导零：
- 如果是数位比较，所以需要前补零（一般为补充下界前导零）
- 反之如果是求各数位的和那么此时前导零没有影响所以不用补零
根据题目的要求来更新答案

例题

无记忆化搜索：纯模板：

class Solution {
    String lowStr;
    String highStr;

    public int countSymmetricIntegers(int low, int high) {
        // 尝试用数位dp v2.0解题
        // 1. 一定有三个参：i, 下界，上界
        lowStr = String.valueOf(low);
        int nLow = lowStr.length();
        highStr = String.valueOf(high);
        // 由于是数位比较，所以前补零
        for (int i = 0; i < highStr.length() - nLow; i++) {
            lowStr = "0" + lowStr;
        }
        // 2. 由于需要判断对称,我们需要sum来记录
        // 2.1 需要判断是前半还是后半
        // 2.2 需要判断前导0
        // 2.3 需要判断从哪里开始，因为 i 只是到了当前位，而当前位我们可以选择填或不填
        // 2.2 和 2.3 可以合并
        return digitDPDFS(0, true, true, -1, 0, 0);
    }

    private int digitDPDFS(int i, boolean limitLow, boolean limitHigh, int start, int prevSum, int afterSum) {
        // System.out.println(i + " " + highStr.length());
        if (i == highStr.length()) {
            if (prevSum == afterSum) return 1; // 说明我们找到了一个合法方案；
            else return 0;
        }

        // 根据limit来确定上界下界
        int lowerBound;
        if (limitLow) lowerBound = lowStr.charAt(i) - '0';
        else lowerBound = 0;
        int higherBound;
        if (limitHigh) higherBound = highStr.charAt(i) - '0';
        else higherBound = 9;

        // System.out.println("lowerBound: " + lowerBound + " " + "HigherBound: " + higherBound);
      	// 如果前面没有填数字，且剩余数位个数是奇数，那么当前数位不能填数字
        if (start < 0 && (highStr.length() - i) % 2 > 0) {
          	// 当前方没有数字（为0）并且此时lowerbound不为0时，我们没有合法方案
            return lowerBound > 0 ? 0 : digitDPDFS(i + 1, true, false, start, prevSum, afterSum);
        }
        
        int res = 0;
        boolean isLeft = start < 0 || i < (start + highStr.length()) / 2;
        for (int d = lowerBound; d <= higherBound; d++) {
            // System.out.println("d: " + d);
            if (isLeft) prevSum += d;
            else afterSum += d;
            res += digitDPDFS(
                i + 1, 
                limitLow && d == lowerBound, 
                limitHigh && d == higherBound, 
                start < 0 && d > 0 ? i : start,
                prevSum, afterSum);
            if (isLeft) prevSum -= d;
            else afterSum -= d;
        }
        return res;
    }
}

含有memo的

2719. 统计整数数目

class Solution {
    static int MOD = 1000000000 + 7;
    int min_sum, max_sum;
    char[] num1Char, num2Char;
    int n;
    int[][][] memo;
    public int count(String num1, String num2, int min_sum, int max_sum) {
        this.min_sum = min_sum;
        this.max_sum = max_sum;
        // 尝试使用dp 2.0 模板解题
        // 1. 补充前导零
        while (num1.length() < num2.length()) {
            num1 = "0" + num1; 
        }
        
        num1Char = num1.toCharArray();
        num2Char = num2.toCharArray();
        
        n = num2Char.length;

        // memo for [i, isNum, curSum]
        memo = new int[n][2][max_sum + 1];
        for (int[][] mat : memo) {
            for (int[] row : mat) {
                Arrays.fill(row, -1);
            }
        }
        
        // 2. 需要 i, limitLow, limitHigh, isNum
        // 2.1 额外的我们需要判断当前数字和: curSum
        return dfs(0, true, true, false, 0);
    }

    private int dfs(int i, boolean limitLow, boolean limitHigh, boolean isNum, int curSum) {
        if (i == n) {
            if (curSum >= this.min_sum && curSum <= this.max_sum) return 1;
            else return 0;
        }
        
        if (curSum > this.max_sum) return 0;
        // System.out.println(i + " " + curSum);

        // 只记录 不 受到 limitLow 或 limitHigh 约束时的状态 i
        // 因为受到影响的不会再被用到，因此无需记忆
        if (!limitLow && !limitHigh && memo[i][isNum ? 1 : 0][curSum] != -1) {
            return memo[i][isNum ? 1 : 0][curSum];
        }

        int res = 0;

        // 跳过，即前方没有数字 (isNum = false) 且当前位为0 (num1Char[i] == '0')
        // 注意此时limitLow一定是true，因为后续的数会被限制
        if (!isNum && num1Char[i] == '0') {
            res = (dfs(i + 1, true, false, false, curSum)) % MOD;
        }

        int lowerBound = limitLow ? num1Char[i] - '0' : 0;
        int upperBound = limitHigh ? num2Char[i] - '0' : 9;
        
        int d0 = isNum ? 0 : 1;
        for (int d = Math.max(d0, lowerBound); d <= upperBound; d++) {
            // System.out.println(i + " " + d + " " + curSum);
            res = (res + dfs(i + 1, limitLow && d == lowerBound, limitHigh && d == upperBound, true, curSum + d)) % MOD;
        }

         if (!limitLow && !limitHigh) {
            memo[i][isNum ? 1 : 0][curSum] = res;
        }

        return res;
    }
}

1399. 统计最大组的数目

class Solution {
    String nStr;
    Map<Integer, Integer> hm = new HashMap<>();
    int[][] memo;
    public int countLargestGroup(int n) {
        // 查看数位是否相等，尝试使用数位dp
        // n 是上界，因此此题没有下界，尝试使用v1.0解题
        // 由于是求数位和那么此时前导零没有影响，不处理
        nStr = String.valueOf(n);
        digitDP(0, true, 0);
        int res = 1;
        int maxValue = -1;
        for (int value : hm.values()) {
            if (value > maxValue) {
                res = 1;
                maxValue = value;
            }
            else if (value == maxValue) res++;
        }
        return res;
    }

    private void digitDP(int i, boolean limitHigh, int digitSum) {
        if (i == nStr.length()) {
            if (digitSum > 0) {
                hm.merge(digitSum, 1, (a, b) -> a + b);
            }
            return;
        }

        int upperBound = limitHigh ? nStr.charAt(i) - '0' : 9;

        for (int d = 0; d < upperBound + 1; d++) {
            digitDP(i + 1, limitHigh && d == upperBound, digitSum + d);
        }
    }
}

// 上边的方法无法记忆化，因为一直累加的话target无法复用

class Solution {
    public int countLargestGroup(int n) {
        char[] s = String.valueOf(n).toCharArray();
        int m = s.length;
        int[][] memo = new int[m][m * 9 + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }

        int maxCnt = 0;
        int ans = 0;
        for (int target = 1; target <= m * 9; target++) { // 枚举目标数位和
            int cnt = dfs(0, target, true, s, memo);
            if (cnt > maxCnt) {
                maxCnt = cnt;
                ans = 1;
            } else if (cnt == maxCnt) {
                ans++;
            }
        }
        return ans;
    }

    private int dfs(int i, int left, boolean limitHigh, char[] s, int[][] memo) {
        if (i == s.length) {
            return left == 0 ? 1 : 0;
        }
        if (!limitHigh && memo[i][left] != -1) {
            return memo[i][left];
        }

        int hi = limitHigh ? s[i] - '0' : 9; // 当前数位至多填 hi
        int res = 0;
        for (int d = 0; d <= Math.min(hi, left); d++) { // 枚举当前数位填 d
            res += dfs(i + 1, left - d, limitHigh && d == hi, s, memo);
        }

        if (!limitHigh) {
            memo[i][left] = res;
        }
        return res;
    }
}

两个问题：

为什么 target 的最大值是 9 * m

在这道题中，我们关注的是每个数字的 数位和，比如：

123 的数位和是 1 + 2 + 3 = 6
999 的数位和是 9 + 9 + 9 = 27

`m` 是 `n` 的位数

你已经通过：

1 2	char[] s = String.valueOf(n).toCharArray(); int m = s.length;

得到了 n 的位数是 m。

每一位的数值最大是 9

十进制中，一个数的每一位最多是 9。所以，m 位数的最大数位和是：

1	9 + 9 + ... + 9 (m 个 9) = 9 * m

所以：当你在枚举 target 的时候

1	for (int target = 1; target <= m * 9; target++)

你是在枚举所有 可能出现的数位和（从 1 到最大值 9 * m），这也就是这个区间的由来。

如果 n = 9999，那：

它是 4 位数 → m = 4
每一位最大是 9 → 最大数位和 = 4 * 9 = 36
所以 target 最大枚举到 36 是没问题的

为什么要把 left 定义成剩余的数位和，而不是已填的数位和？
因为这样可以让 target = 1, 2, ..., 9*m 复用同一个记忆化搜索的结果。
如果反过来，从 0 累加到 target，那么 memo 的内容就和 target 绑定，无法复用。

我们定义 dfs(i, left) 表示从第 i 位开始，还剩下 left 的数位和要分配。

这个“剩余”写法的好处是：

每次递归的目标结构是统一的，只和剩余值有关。
所有 target 值之间的搜索过程是可以共用的。

假设定义：

1	dfs(i, sum) // sum 是当前已填入的数位和

这样做的问题是：

每个 target 都要单独从 sum = 0 开始递归；
那么你记忆化的 memo[i][sum] 是专门为这个 target 服务的；
切换 target 后，memo 不能复用 → 大量重复计算！

假设我们要处理 n = 99 → 两位数 → 最大 target 是 9 * 2 = 18

我们要枚举所有 target = 1~18，看哪些数（在 1~99 范围内）数位和等于 target。

我们用的是：

1	dfs(i, left) // left 是剩下的目标值

例如：

处理 target = 10 的时候会调用：
1
2
3
dfs(0, 10)
dfs(1, 3)
...

处理 target = 12 的时候也会调用：

1
2
3

dfs(0, 12)
dfs(1, 3) ←这个子问题可以复用之前 target=10 的 dfs(1,3) 结果
...

如果是：

1	dfs(i, curSum)

处理 target = 10 和 target = 12 时会分别从 curSum = 0 开始向上累加。
这时候 curSum = 3 是在不同的路径、不同的目标下产生的 → 所以memo 无法共用，只能重新算。

一个详细例子比如 n = 99：为什么 dfs(1, 3) 会在多个 target 中被共用。

我们处理的问题是：

我们使用数位 DP 来统计对于某个 target（数位和）来说，有多少个 x 满足：

x <= n
x 的数位和等于 target

我们定义：

1	dfs(i, left, limitHigh)

i：当前正在填第几位（从左往右）
left：还需要填的数位和
limitHigh：是否受限于原数字 s 的上界（true 代表必须 ≤ n 对应位）

为什么处理 target=10 和 target=12 时，某些子状态（比如 dfs(1, 3)) 是可以共用的。

我们从：

1	dfs(0, 10, true)

开始递归。第一位最多填 9，我们可以枚举 d=0 到 9：

当我们填第一位是 7，就剩下 10 - 7 = 3 要在第二位填完 → 会递归：
1
dfs(1, 3, false) // 不受限了

类似地：

1	dfs(0, 12, true)

枚举第一位是 9 时，还剩下：

1	12 - 9 = 3

所以会递归到：

1	dfs(1, 3, false) // again!

无论是从 target=10 还是 target=12 出发，它们都可能在中间产生：

1	dfs(1, 3, false)

因为这个状态只和「当前是第1位」+「还需要填3的和」+「不受限」有关

如果换成：

1	dfs(i, curSum)

那 target = 10 和 target = 12 的时候，它们的起点不同：

dfs(0, 0, 10)
dfs(0, 0, 12)

在后续过程中你会分别得到 dfs(1, 3, 10) 和 dfs(1, 3, 12)

虽然当前和是 3，但是目标不一样，无法共用状态。

因为 dfs(1, 3) 的含义是：

“从i = 1位（第二位）开始，构造所有数位和为3的合法组合”。

这和前面选的是哪个 target 无关，它只关心 当前位置 和 还剩下多少和要凑。

模板

例题

m 是 n 的位数

`m` 是 `n` 的位数