一、定义
数位是把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。
数位DP通常用来解决一类特定的问题（有通用的模板），这种问题比较好辨认，一般具有这几个特征：
- 要求统计满足一定条件的数的数量（即，最终目的为计数）；
- 这些条件经过转化后可以使用「数位」的思想去理解和判断；
- 输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
- 上界很大，暴力枚举验证会超时。
二、例题
LC2376. 统计特殊整数
如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。
给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。
1
2
3
| >输入：n = 20
>输出：19
>解释：1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。
|
1 <= n <= 2 * 10^9
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
| class Solution {
public:
int countSpecialNumbers(int n) {
string s = to_string(n);
int m = s.size(), dp[m][1<<10];
memset(dp, -1, sizeof(dp));
function<int(int, int, bool, bool)>f = [&](int i, int mask, bool isLimit, bool isNum) -> int {
if (i == m) {
return isNum;
}
if(!isLimit && isNum && dp[i][mask] != -1) {
return dp[i][mask];
}
int ans = 0;
if(!isNum) {
ans = f(i + 1, mask, false, false);
}
int up = isLimit ? s[i] - '0' : 9;
for(int d = 1 - isNum; d <= up; d++) {
if((mask >> d & 1) == 0) {
ans += f(i + 1, mask | (1 << d), isLimit && d == up, true);
}
}
if(!isLimit && isNum) {
dp[i][mask] = ans;
}
return ans;
};
return f(0, 0, true, false);
}
};
|
LC1012. 至少有 1 位重复的数字
https://leetcode.cn/problems/numbers-with-repeated-digits/description/
和上题类似，正难则反。
三、参考
https://www.bilibili.com/video/BV1rS4y1s721/?t=20m05s
