数位dp

数位分解：将一个数按照各个数位进行分解，例如将123分解为1、2、3。数位dp主要涉及到对这些数位的状态进行动态规划，通常，状态表示当前处理到的位置、当前已经得到的数值等信息。

可用于解决如数位上包含特定数字、数字之和等问题。

数位dp模板

2376. 统计特殊整数(2120)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int countSpecialNumbers(int n) {
        char cs[] = String.valueOf(n).toCharArray();
        int memo[][] = new int[cs.length][1 << 10];
        for (int i = 0; i < cs.length; i++) Arrays.fill(memo[i], -1);
        return dfs(0, 0, true, false, cs, memo);
    }
    // i: 当前数位
    // mask: 已经选过的数字
    // isLimit: 是否有上界（例如数字123，如果前两位选取1和2，那么此时有上界，第三位只能选1 2 3）
    // isNum: 是否已经选过数字（例如数字123，如果第一位选择跳过当前数位，则isNum仍为false，否则为true）
    public int dfs(int i, int mask, boolean isLimit, boolean isNum, char cs[], int memo[][]) {
        if (i == cs.length) return isNum ? 1 : 0;
        if (!isLimit && memo[i][mask] != -1) return memo[i][mask];
        int res = 0;
        if (!isNum) res = dfs(i+1, mask, false, false, cs, memo);  // 选择跳过当前数位
        int up = isLimit ? cs[i]-'0' : 9;
        for (int d = isNum ? 0 : 1; d <= up; d++) {  // 选取当前数位
            if ((mask >> d & 1) == 0) res += dfs(i+1, mask|(1<<d), isLimit && d==up, true, cs, memo);
        }
        if (!isLimit && isNum) memo[i][mask] = res;  // isLimit=false isNum=true 的情况不需要记忆化
        return res;
    }
}