数位DP

  |  

摘要: 数位 DP 的算法原理,题目列表以及题解

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


数位 DP 在基础的动态规划问题当中算是比较难的一类,因为数位 DP 的状态的物理意义不太好理解。其它的动态规划,比如区间 DP 状态的物理意义就是区间,状态压缩 DP 中状态的物理意义就是集合,这都比较好理解。

但是数位 DP 比其它 DP 好的一面是数位 DP 的思维相对比较固定。一个是解决的问题模式比较固定,一个是状态设计也比较固定,因此可以通过一些常见问题把数位 DP 的套路了解个大概。

$1 数位DP基本思想

数位 DP 主要解决的问题: 在一段区间 [L, R] 上的以下两类问题。

(1) 满足某些条件的数字个数

(2) 将 $x \in [L, R]$ 代到一个函数 f(x) 中, 一个数字 x 的 f(x) 值为一次贡献的量, 求总的贡献

时间复杂度一般是 $log_{10}L$。

数位 DP 的思考过程

以一个最简单的例子说明数位 DP 的思考过程: [L, R] 上的整数会共有多少个。

首先对于区间 [L, R] 上的问题, 首先变成解决前缀 [0, N] 的问题, [0, N] 上的问题解决后, 求一次 [0, R], 和 [0, L- 1] 就可以得到原问题的解了。

例如 N = 2357。

首先位数的范围是 3 ~ 0, 第 3 位为 2, 第 2 位为 3, 第 1 位为 5, 第 0 位为 7. 在枚举某个位可能的数字的时候, 必须要高位的数字已经确定了, 才能只当当前位的枚举范围。

比如当前为是第 2 位, 如果它的高位第 3 位是 0, 1, 则当前第 2 位的选择范围是 0 ~ 9 , 而当第 3 位为 2, 第 2 为的选择范围就变成 0 ~ 3。

分类:高位的数字可以分成两类, 如果没有顶到上界(例如第 3 位为 2), 则枚举范围就是 0 ~ 9, 即不限制, 而如果高位顶到了上界(例如第 3 位为 2), 当前位的范围就会被限制。

如果当前为枚举的数字因高位顶到了上界而被限制, 则当前位的数字枚举也要分类: 顶到上界, 未顶到上界, 这两种对低位的枚举影响不一样

如图:

  • 当高位未顶到上界(可能是未被限制, 也可能是被限制了但是选的数未顶到上界), 则低位的数字无限制, 可选 0 ~ 9。
  • 当高位顶到了上界, 则低位的数字被限制且要分类: 顶到上界和未顶到上界。

可以看出各个位上未被限制的情况被反复的复用, 这是用数位 DP 可以提高效率的地方。而顶到上界的情况, 只出现一次(图中下面那条链)。

DP 状态设计

dp[pos][lim] , pos 为当前的数位N-1 ~ 0, lim 表示是否顶到上界, 对于 -1 的地方

pos 到 -1 的时候可以 return 1, 使得个位的枚举有效.

DP 状态转移

1
2
3
dp[pos][lim]: 
dp[pos][0] = 10 * dp[pos - 1][0]
dp[pos][1] = digits[i] * dp[pos - 1][0] + dp[pos - 1][1]

因为顶到上界的时候只需要计算一次, 所有 lim 可以不放到 dp 数组里记忆化: 将 dp 数组改为 1 维, 但是在 dfs 的时候带着 lim 这个参数。

有的时候一串前导 0 需要特别处理。此时可以在 dfs 加一个状态 zero, 见后面的例题。

总结

  • 一般数位 DP 的状态必有的维度有 pos, lim
  • 前导零会对结果产生影响时, 加一维 zero
  • 可能需要带上前缀的某种状态 state, 此状态可能影响当前位的枚举, 也可能影响当前位枚举的值对答案的贡献

$2 数位DP题目

902. 最大为 N 的数字组合

给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如,如果 digits = [‘1’,’3’,’5’],我们可以写数字,如 ‘13’, ‘551’, 和 ‘1351315’。

返回 可以生成的小于或等于给定整数 n 的正整数的个数 。

提示:

1
2
3
4
5
6
1 <= digits.length <= 9
digits[i].length == 1
digits[i] 是从 '1' 到 '9' 的数
digits 中的所有值都 不同 
digits 按 非递减顺序 排列
1 <= n <= 1e9

示例 1:
输入:digits = [“1”,”3”,”5”,”7”], n = 100
输出:20
解释:
可写出的 20 个数字是:
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

示例 2:
输入:digits = [“1”,”4”,”9”], n = 1000000000
输出:29523
解释:
我们可以写 3 个一位数字,9 个两位数字,27 个三位数字,
81 个四位数字,243 个五位数字,729 个六位数字,
2187 个七位数字,6561 个八位数字和 19683 个九位数字。
总共,可以使用D中的数字写出 29523 个整数。

示例 3:
输入:digits = [“7”], n = 8
输出:1

算法:数位 DP

也是问 [1, N] 上的数字有多少个, 只是每一位只能用给定的数字, 因此在上面推导过程的基础上, 在转移的时候, 限制枚举的数字种类即可。

代码 (不带前导零状态)

1
2
3
num_set: 可选数字集合
digits[i]: 第 i 位的上界, 在第 i 位若被限制, 则需要取 digits[i]
getdp(...) : dfs

以下为不带前导零状态的数位DP模板。

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
class Solution
{
public:
int atMostNGivenDigitSet(vector<string>& D, int N)
{
set<int> num_set;
for(const string &s: D)
num_set.insert(s[0] - '0');

vector<int> digits;
while(N)
{
digits.push_back(N % 10);
N /= 10;
}

vector<vector<int>> dp(digits.size(), vector<int>(2, -1));
int n = digits.size();
int ans = getdp(n - 1, 1, digits, num_set, dp);
// 上面的计算只能算与 N 等长的数
// 下面把更短的数字可能的贡献加上, 相当于有前导 0
for(int i = 1; i < n; ++i)
ans += getdp(i - 1, 0, digits, num_set, dp);
return ans;
}

private:
int getdp(int pos, int lim, const vector<int>& digits, const set<int>& num_set, vector<vector<int>>& dp)
{
if(pos == -1) return 1;
if(dp[pos][lim] != -1)
return dp[pos][lim];
dp[pos][lim] = 0;
int up = lim ? digits[pos] : 9; // 当前要枚举到的上界
for(int i: num_set) // 枚举当前位所有可能数字
{
if(i > up)
break;
dp[pos][lim] += getdp(pos - 1, lim && i == up, digits, num_set, dp); // 本位被限制且选顶到上界的数字,下一位才被限制
}
return dp[pos][lim];
}
};

代码 (带前导零状态)

增加 zero 状态, 表示高位是否是前导零。

  • 如果高位选了前导零, 则当前位无限制, 且还可以选前导零。
  • 如果高位没有选前导零且为顶到上界, 则当前位在可选数字集合的范围内无限制。
  • 如果高位顶到了上界, 则当前位的选择被限制。

以下为带前导零状态的数位DP模板。

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
class Solution
{
public:
int atMostNGivenDigitSet(vector<string>& D, int N)
{
set<int> num_set;
for(const string &s: D)
num_set.insert(s[0] - '0');

vector<int> digits;
while(N)
{
digits.push_back(N % 10);
N /= 10;
}

vector<int> dp(digits.size(), -1);
int n = digits.size();
int ans = getdp(n - 1, 1, 1, digits, num_set, dp);
return ans;
}

private:
int getdp(int pos, int lim, int zero, const vector<int>& digits, const set<int>& num_set, vector<int>& dp)
{
if(pos == -1) return !zero; // 如果是一直前导零直到 -1
if(dp[pos] != -1 && !zero && !lim) // 关键: !zero 且 !lim 的时候, 才是复用的部分, 见图
return dp[pos];
int ans = 0;
int up = lim ? digits[pos] : 9; // 当前要枚举到的上界
if(zero)
ans += getdp(pos -1, 0, 1, digits, num_set, dp);
for(int i: num_set) // 枚举当前位所有可能数字
{
if(i > up)
break;
ans += getdp(pos - 1, lim && i == up, 0, digits, num_set, dp); // 本位被限制且选顶到上界的数字,下一位才被限制
}
if(!lim && !zero)
dp[pos] = ans;
return ans;
}
};

357. 计算各个位数不同的数字个数

给你一个整数 n ,统计并返回各位数字都不同的数字 x 的个数,其中 0 <= x < 10n 。

提示:

1
0 <= n <= 8

示例 1:
输入:n = 2
输出:91
解释:答案应为除去 11、22、33、44、55、66、77、88、99 外,在 0 ≤ x < 100 范围内的所有数字。

示例 2:
输入:n = 0
输出:1

算法:数位 DP

数位DP的变化主要在前缀状态 state 上面。

1012 题中 state 的含义与本题相同

1
dp[pos][state] : 第 pos 位, 没有顶到上界, 不是前导零, 前缀的数字选择情况为 state 时, 的个数

代码 (C++)

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
class Solution {
public:
int countNumbersWithUniqueDigits(int n) {
if(n == 0) return 1;
vector<int> digits(n, 9);

vector<vector<int>> dp(n, vector<int>((1 << 10) - 1, -1));
int state = 0;
int ans = getdp(n - 1, 1, 1, digits, state, dp);
return ans;
}

private:
using ll = long long;

int getdp(int pos, int lim, int zero, const vector<int>& digits, int& used, vector<vector<int>>& dp)
{
if(pos == -1) return 1; // 数字 0
if(!lim && !zero && dp[pos][used] != -1)
return dp[pos][used];

int ans = 0;
int up = lim ? digits[pos] : 9;
if(zero)
ans += getdp(pos - 1, 0, 1, digits, used, dp);
for(int i = 0; i <= 9; ++i)
{
if(i > up) break;
if(zero && i == 0) continue;
if(used & (1 << i)) continue;
used |= (1 << i);
ans += getdp(pos - 1, lim && i == up, 0, digits, used, dp);
used &= (~(1 << i));
}
if(!lim && !zero) dp[pos][used] = ans;
return ans;
}
};

233. 数字 1 的个数

给定一个整数 n,计算所有小于等于 n 的非负整数中数字 1 出现的个数。

提示:

1
0 <= n <= 1e9

示例 1:
输入:n = 13
输出:6

示例 2:
输入:n = 0
输出:0

算法:数位 DP

数位 DP 的第二类问题: 求贡献。

算贡献的时候带着一个 cnt, cnt 表示前缀中 1 的个数, 当前位选 1 则要将 cnt + 1。

代码 (C++)

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
class Solution {
public:
int countDigitOne(int n) {
if (n <= 0) return 0;
vector<int> digits;
while(n)
{
digits.push_back(n % 10);
n /= 10;
}
int m = digits.size();
vector<vector<vector<int>>> dp(m, vector<vector<int>>(m, vector<int>(2, -1)));
return getdp(m - 1, 1, 0, digits, dp);
}

private:
int getdp(int pos, int lim, int cnt, const vector<int>& digits, vector<vector<vector<int>>>& dp)
{
if(pos == -1) return cnt;
int &ans = dp[pos][cnt][lim];
if(ans != -1) return ans;
ans = 0;
int up = lim ? digits[pos] : 9;
for(int i = 0; i <= up; ++i)
{
ans += getdp(pos - 1, lim && (i == up), cnt + (i == 1), digits, dp);
}
return ans;
}
};

1067. 范围内的数字计数

给定一个在 0 到 9 之间的整数 d,和两个正整数 low 和 high 分别作为上下界。返回 d 在 low 和 high 之间的整数中出现的次数,包括边界 low 和 high。

提示:

1
2
0 <= d <= 9
1 <= low <= high <= 2×10^8

示例 1:
输入:d = 1, low = 1, high = 13
输出:6
解释:
数字 d=1 在 1,10,11,12,13 中出现 6 次。注意 d=1 在数字 11 中出现两次。

示例 2:
输入:d = 3, low = 100, high = 250
输出:35
解释:
数字 d=3 在 103,113,123,130,131,…,238,239,243 出现 35 次。

代码 (C++)

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
class Solution {
public:
int digitsCount(int d, int low, int high) {
return solve(high, d) - solve(low - 1, d);
}

private:
int solve(int N, int d)
{
if(N == 0) return 0;
vector<int> digits;
while(N)
{
digits.push_back(N % 10);
N /= 10;
}
int m = digits.size();
vector<vector<int>> dp(m, vector<int>(m, -1)); // dp[pos][state]
int ans = getdp(m - 1, 1, 1, digits, 0, dp, d);
return ans;
}

int getdp(int pos, int lim, int zero, const vector<int>& digits, int state, vector<vector<int>>& dp, int d)
{
if(pos == -1) return state;
if(!lim && !zero && dp[pos][state] != -1)
return dp[pos][state];
int ans = 0;
if(zero)
ans += getdp(pos - 1, 0, 1, digits, state, dp, d);
int up = lim ? digits[pos] : 9;
for(int i = 0; i <= 9; ++i)
{
if(i > up)
break;
if(zero && i == 0) continue;
ans += getdp(pos - 1, lim && i == up, 0, digits, state + (i == d), dp, d);
}
if(!lim && !zero)
dp[pos][state] = ans;
return ans;
}
};

248. 中心对称数 III

给定两个字符串 low 和 high 表示两个整数 low 和 high ,其中 low <= high ,返回 范围 [low, high] 内的 「中心对称数」总数 。

中心对称数 是一个数字在旋转了 180 度之后看起来依旧相同的数字(或者上下颠倒地看)。

示例 1:
输入: low = “50”, high = “100”
输出: 3

示例 2:
输入: low = “0”, high = “0”
输出: 1

提示:

1
2
3
4
1 <= low.length, high.length <= 15
low 和 high 只包含数字
low <= high
low and high 不包含任何前导零,除了零本身。

算法1:数位DP

本题是力扣中最难的哪一档了 。。。

1
dp[pos][lim]

有对称性的数位 DP, 在 pos 超过中间的时候需要特判, 若前一半没有顶到上界, 后半部分还可以随便选, 但前一半顶到上界了, 后半部分的数字取法就定死了, 没得选.

处理方法:例如 N = 35956, pos = 1 时, 高位选的数为 359,先看高位是 358 的时候, 合法的数有多少种, 然后再特判高位是 359 时, 后面要跟前面对称有没有存在的数。

奇数长和偶数长的问题需要特判。

代码 (C++)

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class Solution {
public:
int strobogrammaticInRange(string low, string high) {
mapping[0] = 0;
mapping[1] = 1;
mapping[8] = 8;
mapping[6] = 9;
mapping[9] = 6;
int result = solve(high) - solve(low) + check(high);
if(result < 0)
return 0;
return result;
}

private:
unordered_map<int, int> mapping;

int getdp(int pos, int lim, int odd, int fi, const vector<int>& digits, vector<vector<vector<int>>>& dp)
{
// fi 的意义与前导零类似
if(pos == -1) return 1;
int ans = dp[pos][lim][odd];
if(!fi && ans != -1) return ans;
ans = 0;
int up = lim ? digits[pos] : 9;
for(int i: {0, 1, 6, 8, 9})
{
if(i > up)
break;
if(fi && i == 0) // 都枚举严格等于长度的 , 最高位严格不是 0
continue;
if(odd && pos == 0 && (i == 6 || i == 9)) // 奇数长的中间位置只能是 0, 1, 8
continue;
ans += getdp(pos - 1, lim && i == up, odd, 0, digits, dp);
}
if(!fi)
dp[pos][lim][odd] = ans;
return ans;
}

int solve(const string& s)
{
if(s == "0") return 0;
int n = s.size();
vector<int> digits;
for(int i = 0; i < (n + 1) / 2; ++i) // 仅枚举前一半
{
digits.push_back(s[i] - '0');
}
reverse(digits.begin(), digits.end());
int m = digits.size();
for(int i = 0; i < m; ++i)
{
if(digits[i] > 0)
{
--digits[i];
break; // N = 35956 的例子中, 将前半部分变为 358
}
digits[i] = 9;
}
int ans = 0;
vector<vector<vector<int>>> dp(m, vector<vector<int>>(2, vector<int>(2, -1)));
if(digits.back() != 0) // 100000, 此时取一半, 前一半未顶上界时, 99 , 位数少了
ans += getdp(m - 1, 1, n & 1, 1, digits, dp);
for(int i = n - 1; i >= 1; --i) // 所有比当前串短的贡献都算一下
ans += getdp((i + 1) / 2 - 1, 0, i & 1, 1, digits, dp);
return ans + 1; // "0"
}

bool check(const string& s)
{
// 处理前缀都顶到上界的情况
// 看后半部分对称过去之后是否合法
int n = s.size();
string ns;
for(int i = 0; i < (n + 1) / 2; ++i)
{
if(!mapping.count(s[i] - '0'))
return false;
}
if((n & 1) && (s[(n - 1) / 2] == '6' || s[(n - 1) / 2] == '9'))
return false;
for(int i = (n + 1) / 2; i < n; ++i)
{
int a = s[i] - '0';
int b = mapping[s[n - i - 1] - '0'];
if(a != b)
return a > b; // 前面一半与限制一样,对称过去的部分只要比限制小就是能取到的
}
return true;
}
};

算法2:回溯

以下是之前没学过数位 DP 时写过的 基于回溯的代码,还是数位 DP 的方法更好。

代码 (C++)

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
47
48
49
50
51
52
53
54
55
class Solution {
public:
int strobogrammaticInRange(string low, string high) {
int min_len = low.size(), max_len = high.size();
int result = 0;
string item;
for(int len = min_len; len <= max_len; ++len)
{
int left = 0, right = len - 1;
item.assign(len, '0');
dfs(left, right, len, low, high, result, item);
}
return result;
}

private:
vector<char> chars = {'0','1','6','8','9'};
vector<char> chars_reverse = {'0','1','9','8','6'};

void dfs(int left, int right, int len, const string& low, const string& high, int& result, string& item)
{
int min_len = low.size(), max_len = high.size();

if(left > right)
{
if((len > min_len || item >= low) && (len < max_len || item <= high))
++result;
return;
}

if(left == right)
{
for(char ch: vector<char>{'0', '1', '8'})
{
item[left] = ch;
if((len > min_len || item >= low) && (len < max_len || item <= high))
++result;
item[left] = '0';
}
return;
}

// left < right
for(int i = 0; i < (int)chars.size(); ++i)
{
char ch = chars[i];
if(left == 0 && ch == '0') continue;
item[left] = ch;
item[right] = chars_reverse[i];
dfs(left + 1, right - 1, len, low, high, result, item);
item[left] = '0';
item[right] = '0';
}
}
};

1088. 易混淆数 II

易混淆数(Confusing Number)指的是一个数字在整体旋转 180° 以后,能够得到一个和原来 不同 的数,且 新数字的每一位都应该是有效的。

本题我们会将数字旋转 180° 来生成一个新的数字。

  • 当 0、1、6、8、9 旋转 180° 以后,我们得到的新数字分别为 0、1、9、8、6。
  • 当 2、3、4、5、7 旋转 180° 后,是 无法 得到任何数字的。

请注意,在旋转一个数字之后,我们可以忽略前导零。

  • 例如,在旋转 8000 之后,我们有 0008 ,它被认为只是 8 。

给出正整数 n,请你返回 [1, n] 范围内的 易混淆数 的数量 。

示例 1:
输入:n = 20
输出:6
解释:易混淆数为 [6,9,10,16,18,19]。
6 转换为 9
9 转换为 6
10 转换为 01 也就是 1
16 转换为 91
18 转换为 81
19 转换为 61

示例 2:
输入:n = 100
输出:19
解释:易混淆数为 [6,9,10,16,18,19,60,61,66,68,80,81,86,89,90,91,98,99,100]。

提示:

1
1 <= n <= 1e9

算法:数位 DP

上一题 248. 中心对称数 III 是找翻过来看起来一样的, 本题是找翻过来看起来不一样的. 因此可以先找出翻过来看起来一样的 A, 然后将所有可能的数的个数减去 A.

而所有可能的数的个数就是902. 最大为 N 的数字组合. 因此本题是两道题合并了一下.

代码 (D++)

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
class Solution {
public:
int confusingNumberII(int N) {
// lc248
mapping[0] = 0;
mapping[1] = 1;
mapping[8] = 8;
mapping[6] = 9;
mapping[9] = 6;
int positive_cnt = solve(to_string(N)) - 1 + check(to_string(N));
positive_cnt = max(positive_cnt, 0);

// lc902
set<int> num_set({0, 1, 6, 8, 9});
vector<int> digits;
while(N)
{
digits.push_back(N % 10);
N /= 10;
}
int m = digits.size();
vector<int> dp(m, -1);
int cnt = getcnt(m - 1, 1, 1, digits, dp, num_set);
return cnt - positive_cnt;
}
private:
unordered_map<int, int> mapping;

// lc902
int getcnt(int pos, int lim, int zero, const vector<int>& digits, vector<int>& dp, const set<int>& num_set)
{
if(pos == -1) return !zero;
if(!lim && !zero && dp[pos] != -1)
return dp[pos];
int ans = 0;
if(zero)
ans += getcnt(pos - 1, 0, 1, digits, dp, num_set);
int up = lim ? digits[pos] : 9;
for(int i: num_set)
{
if(i > up)
break;
if(zero && i == 0) continue;
ans += getcnt(pos - 1, lim && i == up, 0, digits, dp, num_set);
}
if(!zero && !lim) dp[pos] = ans;
return ans;
}

// lc 248
int getdp(int pos, int lim, int odd, int fi, const vector<int>& digits, vector<vector<vector<int>>>& dp)
{
// fi 的意义与前导零类似
if(pos == -1) return 1;
int ans = dp[pos][lim][odd];
if(!fi && ans != -1) return ans;
ans = 0;
int up = lim ? digits[pos] : 9;
for(int i: {0, 1, 6, 8, 9})
{
if(i > up)
break;
if(fi && i == 0) // 都枚举严格等于长度的 , 最高位严格不是 0
continue;
if(odd && pos == 0 && (i == 6 || i == 9)) // 奇数长的中间位置只能是 0, 1, 8
continue;
ans += getdp(pos - 1, lim && i == up, odd, 0, digits, dp);
}
if(!fi)
dp[pos][lim][odd] = ans;
return ans;
}

int solve(const string& s)
{
if(s == "0") return 0;
int n = s.size();
vector<int> digits;
for(int i = 0; i < (n + 1) / 2; ++i) // 仅枚举前一半
{
digits.push_back(s[i] - '0');
}
reverse(digits.begin(), digits.end());
int m = digits.size();
for(int i = 0; i < m; ++i)
{
if(digits[i] > 0)
{
--digits[i];
break; // N = 35956 的例子中, 将前半部分变为 358
}
digits[i] = 9;
}
int ans = 0;
vector<vector<vector<int>>> dp(m, vector<vector<int>>(2, vector<int>(2, -1)));
if(digits.back() != 0) // 100000, 此时取一半, 前一半未顶上界时, 99 , 位数少了
ans += getdp(m - 1, 1, n & 1, 1, digits, dp);
for(int i = n - 1; i >= 1; --i) // 所有比当前串短的贡献都算一下
ans += getdp((i + 1) / 2 - 1, 0, i & 1, 1, digits, dp);
return ans + 1; // "0"
}

bool check(const string& s)
{
// 处理前缀都顶到上界的情况
// 看后半部分对称过去之后是否合法
int n = s.size();
string ns;
for(int i = 0; i < (n + 1) / 2; ++i)
{
if(!mapping.count(s[i] - '0'))
return false;
}
if((n & 1) && (s[(n - 1) / 2] == '6' || s[(n - 1) / 2] == '9'))
return false;
for(int i = (n + 1) / 2; i < n; ++i)
{
int a = s[i] - '0';
int b = mapping[s[n - i - 1] - '0'];
if(a != b)
return a > b; // 前面一半与限制一样,对称过去的部分只要比限制小就是能取到的
}
return true;
}
};

788. 旋转数字

我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后,我们仍可以得到一个有效的,且和 X 不同的数。要求每位数字都要被旋转。

如果一个数的每位数字被旋转以后仍然还是一个数字, 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己;2 和 5 可以互相旋转成对方(在这种情况下,它们以不同的方向旋转,换句话说,2 和 5 互为镜像);6 和 9 同理,除了这些以外其他的数字旋转以后都不再是有效的数字。

现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数?

提示:

1
N 的取值范围是 [1, 10000]。

示例:
输入: 10
输出: 4
解释:
在[1, 10]中有四个好数: 2, 5, 6, 9。
注意 1 和 10 不是好数, 因为他们在旋转之后不变。

代码 (C++)

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
class Solution {
public:
int rotatedDigits(int N) {
num_set = {2, 5, 6, 9};
return solve(N);
}

private:
unordered_set<int> num_set;
int solve(int n)
{
vector<int> digits;
while(n)
{
digits.push_back(n % 10);
n /= 10;
}
int m = digits.size();
vector<vector<int>> dp(2, vector<int>(m, -1));
int ans = getdp(m - 1, 1, 1, 0, digits, dp);
return ans;
}

int getdp(int pos, int lim, int zero, int state, const vector<int>& digits, vector<vector<int>>& dp)
{
if(pos == -1) return state == 1;
if(!zero && !lim && dp[state][pos] != -1)
return dp[state][pos];
int ans = 0;
if(zero)
ans = getdp(pos - 1, 0, 1, 0, digits, dp);
int up = digits[pos];
for(int i: {0, 1, 2, 5, 6, 8, 9})
{
if(lim && i > up) break;
if(i == 0 && zero)
continue;
ans += getdp(pos - 1, lim && i == up, 0, state || num_set.count(i) > 0, digits, dp);
}
if(!zero && !lim)
dp[state][pos] = ans;
return ans;
}
};

$3 数位 DP 其它题目

1.

$F(x) = A_{n}2^{n-1} + A_{n - 1}2^{n-2} + … + A_{1}2^{0}$, 给定A, [L, R] 有多少数字 x 满足 $F(x) < F(A)$

1
2
3
4
5
dp[pos][lim]
sum 在 dfs 的过程中带着, 表示贡献
当前数字选 i: 产生 i* 2 ^ (pos - 1) 的贡献
将该贡献从 sum 中减去
当 sum < 0 的时候就到上界了

2.

求 [1, N] 中的数字个数, 要求至少出现一次 “49” 子串。

1
2
dp[pos][lim][f][pre]
pos, lim 为常规的数位 dp 的状态, f 表示 "49" 是否出现过, pre 表示高位是否为 4

可以逆向思维, 找不包含 49 的数字, 这样状态可以少一维。

1
2
dp[pos][lim][pre]
pos, lim 为常规的数位 dp 的状态, pre 表示高位是否为 4

3.

求 [L, R] 中的数字个数, 不可出现 “62” 子串, 且不能出现 “4”。

与上一题几乎一样, [L, R] 的处理: [0, L - 1], [0, R] 两个问题分别求一次。

4.

[L, R], 相邻数字差至少为 2。

1
dp[pos][lim][pre][zero]

5.

[L, R] 二进制表示中 0 的个数不少于 1 的个数。

在模板代码的十进制分解部分:

1
2
3
4
5
6
vector<int> digits;
while(N)
{
digits.push_back(N % 10);
N /= 10;
}

改成二进制分解:

1
2
3
4
5
6
vector<int> digits;
while(N)
{
digits.push_back(N % 2);
N /= 2;
}

在二进制的基础上,数位 DP 算法如下:

1
2
3
4
5
dp[pos][lim][cnt0][cnt1]
cnt0: 非前导 0 的 0 的个数
cnt1: 1 的个数
前导零的状态 zero 可以不加: 当 0 出现且是前导零的时候, cnt1 一定得是 0
pos = -1 时, 通过 cnt0 和 cnt 1 判断数字是否合法

6.

[L, R] 能被 x 整除, 且只能用给定数字。

1
2
dp[pos][lim][mod]
当 pos = -1, mod 为 0 是合法的

Share