数位DP模板

0x00 模版特征

1给定我们一个整数 $n$，让我们在范围 $[0,n]$ 之内求符合题目要求的数的个数

0x01 模版引入

1. 题目

统计特殊整数

2. 思路

首先，对于数位 $dp$ 的题目，解决方法就是记忆化搜索。
在明确了解决方法的前提下（$dp$ + 记忆化搜索），我们开始套 $dp$ 的模版。

1. 状态表示：$dp[i][mask]$ 表示当前选择顺位为 $i$，已经选择了的数的状态为 $j$，构造第 $i$ 位及后面位（直到结束）的最大合法方案数。
2. 状态计算：根据最后一个不同点，（第 $i-1$ 位的状态 ）来选择第 $i$ 位的状态（其实这里说是第 $i$ 位不太准确，准确来说应该是从开始直到第 $i-1$ 位）。如果前面 $i-1$ 位等于给定数 $m$ 的前 $i-1$ 位，那么第 $i$ 位的选择是受限制的，否则，$i$ 可以任意取（其实也受限）。

下面解释一下状态计算。
假如给定数字 $m$ 是 $12345$，$m[0]=1,m[1]=2,..,m[4]=5$，我们可以选择的数字为 $s$， 当前处于第 $2$ 位，$i=2$，即 $m$ 中数字 $3$ 所在位置。

如果前面 $i-1$ 如果是 $12$，则 $k[2]=0,1,2,3$，即，$k$ 的第 $i$ 为最高只能取 $3$，否则最高可以取到 $9$。（很好理解）
但是，我们无法通过第 $i-1$ 位就得知前 $i-1$ 位的信息，所以我们需要记录的最后的状态应该是前 $i-1$ 位是否等于 $m$ 的前 $i-1$ 位。（$is\_limit$）

需要用到的变量

好了，现在我们知道我们至少需要两个变量：一个表示当前选择的数 $k$ 的前 $i-1$ 位是否等于 $m$ 的前 $i-1$ 位。（$is\_limit$）。如果等于，即受限制，则为真。
另一个则表示当前遍历到第几个数了（$u$）。
另外，由于题目要求不能出现重复的数字，所以我们还需要判重，由于 $0-9$ 一共才 $10$ 个数字，所以我们不必使用额外数组，哈希表之类，那太大材小用了，我们只需要一个整数（$mask$）即可，充分利用二进制的性质，用整数二进制下第 $i$ 位是否为 $1$ 来表示第 $i$ 位是否被用，这样我们只需要 $O(1)$ 的空间。
别以为这样就完了，通过题目给出的实例可以发现，最后的数 $k$ 不一定和 $m$ 的位数相同，$k=12,123,12345$ 都是可以的，我们应该增加一个变量（$i{s}_{n}um$）表示我们是否已经开始放置数字了，如果放置数字了，那么接下来的所有位都必须放置数字，不能跳过。$12[]45$，这种在 $12$ 和 $45$ 之间跳过了一位肯定是不合理的。如果跳过，则为真，只有该状态为真时，才可以继续跳过。

为啥可以用记忆化

例如，$m=54321$，当前 $k=12???$ 或者 $k=21???$，? 表示还没选，那么这两个 $k$ 构成的方案数肯定是一样的。所以说我们可以保存其中一个的方案数，下一次用到直接使用，而不是再计算一次。
上例也间接说明了，方案数只与 $u$ 和 $mask$ 有关，也就是我们定义的 $dp$ 数组的两维。
但是，这里有一个限制，那就是当 $is\_limit$ 为真时，不可以用记忆化得到的答案。
例如还是上面的 $m$，$k=54???$ 和 $k=45???$ 得到的方案数是不一样的（显然，$k=54???$受约束），所以我们不能用 $k=45???$ 得到的答案更新 $k=54???$ 的方案数，

一段代码的理解

int up = is_limit ? s[u] - '0' : 9;
int low = is_num ? 0 : 1;

这里的 $up$ 容易理解，如果没有限制，可以取到9。
当我们跳过 $cnt$ 个数之后，下一个数如果不跳过，肯定不能选 $0$，否则和跳过没啥区别。所以当 $i{s}_{n}um$ 为真时，我们最小只能取 $1$。
注意！我们不能合并代码：

if(!is_num)     res += f(u + 1, mask, false, false);
int up = is_limit ? s[u] - '0' : 9;
int low = is_num ? 0 : 1;
for(int i = low; i <= up; i ++ )         

为：

int up = is_limit ? s[u] - '0' : 9;
for(int i = 0; i <= up; i ++ )         

因为这样会出现 $12[]45$ 的情况，即数字的中间被跳过了。
总之，我们要区分跳过和填充 $0$ 在什么情况下是合适的：

1. 如果是 $[][][cur][][]$ 的形式，此时 $i{s}_{n}um$ 为 $false$，那么 $cur$ 不能为 $0$，否则等价于跳过，但是跳过的情况我们已经特殊处理了。
2. 如果是 $[][a][cur][][]$ 的形式，此时 $i{s}_{n}um$ 为 $true$，那么 $cur$ 可以为 $0$，但是不能跳过。

代码解释

if(!is_limit)  dp[u][mask] = res;

为啥要加 $i{s}_{l}imit!=0$，因为有 $limit$ 限制的数的情况我们只会搜索一次，因为不需要记忆化。我们只需要记忆化那些被重复搜索的。

3. 自己理解写的代码

class Solution {
public:
    int countSpecialNumbers(int m) {
        string s = to_string(m);
        int n = s.length();
        int dp[n + 1][1 << 10];
        memset(dp, -1, sizeof dp);
        
        function<int(int, int, bool, bool)> f = [&](int u, int mask, bool is_limit, bool is_num) -> int
        {
            if(u == n)  return is_num;
            if(dp[u][mask] != -1 && !is_limit)  return dp[u][mask];
            
            int res = 0;
            if(!is_num)     res += f(u + 1, mask, false, false);
            int up = is_limit ? s[u] - '0' : 9;
            int low = is_num ? 0 : 1;
            for(int i = low; i <= up; i ++ )
            {
                if((mask >> i & 1) == 1)    continue;
                res += f(u + 1, mask | (1 << i), is_limit && i == up, true);
            }
            if(!is_limit)  dp[u][mask] = res;
            return res;
        };
        
        return f(0, 0, true, false);
    }
};

4. 题解带注释代码

class Solution {
public:
    int countSpecialNumbers(int n) {
        // 返回 1～n之间特殊整数的数目
        // 特殊整数：数字中各位互不相同
        string s = to_string(n);
        int m = s.length();
        int dp[10][1 << 10]; /* 1<<10很有说法 */
        // dp[i][j] 标识当前选择顺位为i，已经选择状态为j，构造第i位及后面位的合法方案数
        // 例如对于 n=12345
        // a=10***
        // b=01***
        // a和b能构造的特殊数字是相同的，所以说我们我们对a搜索一次，对b搜索一次，就会造成一次重复搜索
        // 因此我们需要用记忆化来消除重复搜索
        memset(dp, -1, sizeof dp);
        
        function<int(int, int, bool, bool)> f = [&](int i, int mask, bool is_limit, bool is_num) -> int
        {
            
            // 越过最后一位了,此时如果不是全部跳过（为空），就是一个合法解
            if(i == m) return is_num; 
            
            // 是否已经搜索过了
            // 记忆化去掉重复计算 **关键所在**
            // 如果已经计算过该状态：dp[i][mask] >= 0，这一点好理解，只有计算过才能修改数值
            // 并且该状态是有效的：!is_limit && is_num，重点是为啥加上这个
            // 首先，当前位是不能有限制的，例如还是n=54321
            // 我们不可能对形如a=1****,12***,123**,1234*的形式进行重复搜索
            // 通过上面的10***,01***你应该可以看出来，10和01之后的***具有相同的**选择特征**，即可以随便选
            // 所以说它们的搜索是相同的，但是对a=1****,12***,123**,1234*的形式
            // a的搜索是受限制的，也就是说后面的***不能随便选1-9
            // 另外，当前数字必须是有效的，为啥呢？
            // 。。。
            // 其实受限制和为空（无效）这两种情况整个搜索只会出现一次，不存在和他同类型的重复搜索
            // 如果我们利用其他搜索得出的结果代替他，显然是不对的。
            
            // 例如n=54321
            // a=543**,b=345**
            // 此时虽然i和mask相等，但不能代替
            
            // 去掉is_num也能过？？？
            // 
            
            // if(dp[i][mask] != -1 && !is_limit && is_num)    return dp[i][mask];
            if(dp[i][mask] != -1 && !is_limit)    return dp[i][mask];
            
            int res = 0;
            if(!is_num) res = f(i + 1, mask, false, false); // skip to next
            for(int d = 1 - is_num, up = is_limit ? s[i] - '0' : 9; d <= up; d ++ )
            {
                if((mask >> d & 1) == 0)    // not used
                {
                    res += f(i + 1, mask | (1 << d), is_limit && d == up, true);
                }
            }
            if(!is_limit && is_num)    dp[i][mask] = res;
            return res;
        };
        // 一开始最高位是有限制的，如果没有限制的话，那么第0位可以任选，这肯定是不合理的。
        return f(0, 0, true, false);
    }
};

5. 别人写的注释

class Solution {
    int[][] memo;   // memo[i][mask]记录当前选择顺位为i，已选状态为mask时，构造第i位及后面位的合法方案数
    char[] s;

    public int countSpecialNumbers(int n) {
        /*
        参考灵神の数位DP记忆化DFS模板：
        注意这题与LC1012是一样的，不过这题更直接求每一位都不相同数字
        dfs(i, mask, isLimit, hasNum) 代表从左到右选到第i个数字时(i从0开始)，前面数字已选状态为mask时的合法方案数
        各个参数的含义如下:
        i:当前选择的数字位次，从0开始
        mask:前面已择数字的状态，是一个10位的二进制数，如:0000000010就代表前面已经选了1
        isLimit:boolean类型，代表当前位选择是否被前面位的选择限制了；
            如n=1234，前面选了12，选第3位的时候会被限制在0~3，isLimit=true；否则是0~9，isLimit=false
        hasNum:表示前面是否已经选择了数字，若选择了就为true(识别直接构造低位的情况)
        时间复杂度:O(1024*M*10) 空间复杂度:O(1024*M)
        记忆化DFS的时间复杂度=状态数*每一次枚举的情况数
        **记忆化本质就是减少前面已选状态一致的情况，将1eM的时间复杂度压缩至1<<M，效率非常高**
         */
        s = String.valueOf(n).toCharArray();    // 转化为字符数组形式
        int m = s.length;
        memo = new int[m][1 << 10];     // i∈[0,m-1]，mask为一个10位二进制数
        // 初始化memo为-1代表该顺位下该已选状态还没进行计算
        for (int i = 0; i < m; i++) {
            Arrays.fill(memo[i], -1);
        }
        // 注意一开始最高位是有限制的，isLimit=true
        return dfs(0, 0, true, false);
    }

    // dfs(i, mask, isLimit, hasNum) 代表从左到右选第i个数字时，前面已选状态为mask时的合法方案数
    private int dfs(int i, int mask, boolean isLimit, boolean hasNum) {
        // base case
        // i越过最后一位，此时前面选了就算一个，没选的就不算，因为不选后面也没得选了
        if (i == s.length) return hasNum ? 1 : 0;
        // 已经计算过该状态，并且该状态是有效的，直接返回该状态
        // 这一步是降低时间复杂度的关键，使得记忆化dfs的时间复杂度控制得很低
        // !isLimit表示没有被限制的才可以直接得出结果，否则还要根据后面的数字进行计算子问题计算
        if (!isLimit && hasNum && memo[i][mask] != -1) return memo[i][mask];
        int res = 0;    // 结果
        // 本位可以取0(可直接构造低位数)的情况，此时要加上构造低位数0xxx的方案数
        // 将是否选了数字作为分类条件是为了避免出现00010这样有多个0的就不能统计了
        if (!hasNum) res = dfs(i + 1, mask, false, false);
        // 构造与当前顺位相同位数的数字就要枚举可选的数字进行DFS
        // 枚举的起点要视hasNum而定，如果前面选择了数字，那么现在可以选0；否则只能从1开始
        // 枚举得终点视isLimit而定，若被限制了只能到s[i]，否则可以到9
        for (int k = hasNum ? 0 : 1, end = isLimit ? s[i] - '0' : 9; k <= end; k++) {
            // 如果该数字k还没有被选中，那猫就可以选该位数字
            if (((mask >> k) & 1) == 0) {
                // 方案数遵循加法原理
                // i:进行下一位的DFS，因此为i+1
                // mask:由于该位选中了k，mask掩膜传下去就要更新，已选状态加上k
                // isLimit:当且仅当前面的被限制了且该位被限制
                // hasNum:该位选了必定为true
                res += dfs(i + 1, mask | (1 << k), isLimit && k == end, true);
            }
        }
        if (!isLimit && hasNum) memo[i][mask] = res;    // 如果前面没有限制，表明后面都是同质的，可以记录进memo中
        return res;
    }
}

0x02 例题

1. 数字1的个数

1.1 思路

由于本题前导 $0$ 不影响结果，所以不再需要这个参数。
这里的 $dp[i][j]$ 表示当前顺位到第 $i$，已经有 $j$ 个 $1$ 的方案数。第二维是必要的，例如 n = $55555$，那么 $11???$ 和 $34???$ 的方案数肯定是不同的。
参考

1.2 代码

class Solution {
public:
    int countDigitOne(int m) {
        string s = to_string(m);
        int n = s.length();
        int dp[n][n]; // dp[i]：当前位即之后所有位能构成的所有方案中 1 的个数
        memset(dp, -1, sizeof dp);
        
        function<int(int, int, bool)> f = [&](int u, int cnt, bool is_limit) -> int {
            if(u == n)  return cnt;
            
            if(dp[u][cnt] != -1 && !is_limit)    return dp[u][cnt];
            
            int res = 0;
            
            // if(!is_num) res = f(u + 1, cnt, false, false);
                
            int up = is_limit ? s[u] - '0' : 9;
            for(int i = 0; i <= up; i ++ )
            {
                res += f(u + 1, cnt + (i == 1), is_limit && (i == up));
            }
            
            if(!is_limit)  dp[u][cnt] = res;
            return res;
        };
        
        int res = f(0, 0, true);
        return res;
    }
};

2.不含连续1的非负整数

2.1 思路

这一题由于题目要求我们不能在二进制的角度上包含连续的 $1$，所以说我们不能再按照数字的十进制下可以选（$09$）的数转移状态，而是要按照二进制下可以选的数（$01$）转移状态。
另外再说一下，我们的数字都是由限制的（$i{s}_{l}imit$），我们需要记录限制是否存在才能判断这个数起码时合法的（$<=n$），我们只有从数字的高位开始遍历，才能知道这个数是否受限制，从低位遍历是无法判断的，所以说，这里我们要从二进制的高位开始遍历。
另外，很显然我们需要一个变量来记录上一位是否为 $1$，这样我们才能判断该位能否选 $1$。
剩下的就看代码吧。

2.2 代码

class Solution {
public:
    int findIntegers(int m) {
        // 得到 m 的最高位是第几位
        int n = 0;
        for(int i = 30; i >= 0; i -- ) {  
            if(m >> i & 1)  {
                n = i;
                break;
            }
        }
        cout << "n: " << n << ' ' << __lg(m) << endl;
        
        // dp[n][pre] 表示当前顺位到第n位，选择第 n 位及后面所有位并且第 n - 1 位选择的数位 pre 的方案数
        // 这里不需要判断前导 0，因为 0 对答案没有影响
        int dp[n + 1][2];   // 多开一点总没问题
        memset(dp, -1, sizeof dp);
        
        function<int(int, bool, bool)>f = [&](int u, bool pre, bool is_limit) -> int {
            // 使用 bool 类型存储上一位是 0/1 可以节省空间，虽然没啥用
            if(u < 0)   return 1;
            if(!is_limit && dp[u][pre] != -1) return dp[u][pre];
            
            int res = 0;
            bool up = is_limit ? (m >> u & 1) : 1;
            res = f(u - 1, 0, is_limit && (up == 0));
            if(!pre && up)  // 只有不超过限制 (<=m) 并且上一位不是 1 才可以选 1
                res += f(u - 1, 1, is_limit && (up == 1));
            if(!is_limit)   dp[u][pre] = res;
            return res;
        };
        
        return f(n, 0, true);
    }
};

3.至少有 1 位重复的数字

3.1 思路

这道题还是比较考验思维能力的，直接求至少有一位重复数字并不好求，例如 $m=55555$，$k=12???$ 和 $k=11???$，我们不能用前面的 $k$ 得到的方案数取更新后面的 $k$，因为后面的 $k$ 本身就符合条件，后三个数任选就行，但是对于前面的 $k$ 就不可以任选了。
但是！求不包含重复数字的个数还是很好求的。因此，我们逆向思维。 用总数字个数减去不包含重复的就是包含重复的了。

3.2 代码

class Solution {
public:
    int numDupDigitsAtMostN(int m) {
        string s = to_string(m);
        int n = s.length();
        int dp[n][1 << 10];
        memset(dp, -1, sizeof dp);
        
        function<int(int, int, bool, bool)> f = [&](int u, int mask, bool is_limit, bool is_num) -> int {
            
            if(u == n)  return is_num;
            if(dp[u][mask] != -1 && !is_limit && is_num)  return dp[u][mask];
            
            int res = 0;
            if(!is_num) res += f(u + 1, mask, false, false);
            
            int up = is_limit ? s[u] - '0' : 9;
            int low = is_num ? 0 : 1;
            for(int i = low; i <= up; i ++ )
            {
                if(mask >> i & 1)  continue;
                res += f(u + 1, mask | (1 << i), is_limit && (i == up), true);
            }
            
            if(!is_limit && is_num)  dp[u][mask] = res;
            return res;
        };
        
        int res = f(0, 0, true, false);
        // cout << "res: " << res << endl;
        return m - res;
    }
};

0x03 参考

作者用到的C++新特性 function<>


思路&&相似题目&&模板


int stoi(string s)，字符串转 $int$ ，需要保证转换的字符串不能为空，转换后不能大于 $int$ 的范围。

0x04 其他题目

https://www.acwing.com/activity/content/problem/content/1009/