Digit DP
2023-11-27 21:14:43 # Algorithm #DP

数位dp适用的题型

常见的问题是求解在一定范围内（例如从1到N）满足某种条件的数字的数量。例如，求解在1到N之间的所有数字中，包含某种特定数字的数量。

高位数字会影响低位的数字的选择

数位DP的思想是将数字从高位到低位依次考虑，定义状态并进行动态规划。为了方便处理，通常会将数字N转换为一个char类型数组，方便按位处理。

集合与位运算基础

如何用二进制x来表示一个集合？

Given 一个集合{0,2,3}, 用二进制表示为x = 1101

二进制填写的时候从右往左看
第0位对应元素0，因为元素0在集合中，所以第0位是1。
第1位对应元素1，因为元素1不在集合中，所以第1位是0。
第2位对应元素2，因为元素2在集合中，所以第2位是1。
第3位对应元素3，因为元素3在集合中，所以第3位是1。

判断元素d是否在集合中

判断元素d是否在集合中：x>>d & 1

  • 将集合中的第d位元素，【右移】到第0位，判断这个元素是不是1，如果是1，说明在集合中，如果是0，说明不在集合中

添加元素d到集合中

把元素d添加到集合中：x | (1<<d)

  • 将二进制数1左移d位。这个操作的效果就像是在第d位上添加一个1，而其他位都是0
  • 然后将x与上一步的操作进行“或”操作，因为OR操作的特点是，不论x的第d位原来是0还是1，这个操作之后都会变为1，这就实现了把元素d添加到集合中的功能

数位dp模版

以LC2376为例

状态：

  • 当前考虑的位数i（从左到右）
  • 已经考虑过的数字集合mask（从左到右）
    • 可根据题意改变，这里的mask是为了检查重复
  • 是否已经有数字被填充isNum -》针对leading zeros的情况
    • 看题目是否需要考虑区别leading zeros，例如 0102 和 102 是否会对答案有不同的影响。
  • 是否受限于目标数n的上界isLimit

状态表示

int count(int i, int mask,boolean isLimit, boolean isNum)

  • 在位置i处填写数字，前面已经填写的数字为mask，这种情况下有多少个方案数（0或1），这道题是统计特殊整数，比如12是一个特殊整数，而不是去统计它里面有几个数字

状态转移方程:

  • 当isNum为false时，表示前面有leading zeros，当前i位数字有两种选择

    • 第一个选择：选择0，即直接跳过，不能显式的表示0，因为这样会违反题意中的distinct
    • 第二个选择：选择1-9

  • 当isNum为true时，表示前面有数字, 当我们选择填入数字时，我们需要确保这个数字还没有被使用过

    • 当isLimit为true时，表示当前i位数字需要限制在s[i]的范围
    • 当isLimit为false时，表示当前i位数字可以为[0..9]

记忆化搜索：因为是要对重复计算进行记忆化搜索，我们发现当isLimit为false且isNum为true的时候，会有重复，所以我们不考虑isLimit和isNum作为memo中的维度 =》memo[s.length()][1 << 10]，只考虑位数和集合的维度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class CountSpecialIntegers {
    char[] s;
    int[][] memo;
    public int countSpecialNumbers(int n) {
        s = String.valueOf(n).toCharArray();
        int m = s.length;
        memo = new int[m][1<<10];
        for (int i = 0; i < m; i++)
            Arrays.fill(memo[i], -1); // -1 表示没有计算过
        return count(0,0,true,false);
    }

    /**
     * 填充第i位，前面已填充数字为mask
     * @param i
     * @param mask
     * @return
     */
    public int count(int i, int mask,boolean isLimit, boolean isNum){
        if(i==s.length){
            //当前算一个
            return isNum?1:0;
        }
        //记忆化
        if(!isLimit && isNum && memo[i][mask]!=-1){
            return memo[i][mask];
        }
        int res = 0;
        //可以选择跳过当前位置，不填数字(也就是为0的情况)
        if(!isNum){
            res+=count(i+1,mask,false,false);
        }
        //也可以选择不跳过当前位置，填数字(如果没有limit就是[0,up]，limit就是[1,up])
        int up = isLimit?s[i]-'0':9;
        for(int d = isNum?0:1;d<=up;d++){
            //d不在mask中，以保证数字只被使用过一次，是distinct的
            if((mask>>d&1)==0){
                res+=count(i+1,mask | (1<<d),isLimit && d==up,true);
            }
        }
        if(!isLimit && isNum){
            memo[i][mask]=res;
        }
        return res;
    }
}

数组dp秒杀题

LC233 数字1的个数

看题目考虑是否需要区别leading zeros，例如 0102 和 102 是否会对答案有不同的影响。

本题只需要统计 1，按照有前导零的方式统计，还是按照没有前导零的方式统计，算出来的结果是一样的，所以不需要考虑是否有前导零。

只靠【填写到第i位】并不能确定唯一的答案，比如10_ 和 20_，都是在填写第2位，但答案实际上不一样，不能用做记忆化搜索，因此需要确定另一个状态，也就是已经存在多少个1 -> count

其他题

  • 面试题 17.06. 2出现的次数

  • LC600. 不含连续1的非负整数

  • LC902. 最大为 N 的数字组合

  • LC1067. 范围内的数字计数

  • LC1397. 找到所有好字符串（有难度，需要结合一个经典字符串算法）

参考

灵神

Prev
2023-11-27 21:14:43 # Algorithm #DP
Next