题目简介：
给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如，如果 digits =['1','3','5']，我们可以写数字，如 ‘13’, ‘551’, 和 ‘1351315’。
返回 可以生成的小于或等于给定整数 n 的正整数的个数 。
示例 1：
1
2
3
4
5
| 输入：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：
1
2
3
4
5
6
7
| 输入：digits = ["1","4","9"], n = 1000000000
、输出：29523
解释：
我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，
81 个四位数字，243 个五位数字，729 个六位数字，
2187 个七位数字，6561 个八位数字和 19683 个九位数字。
总共，可以使用D中的数字写出 29523 个整数。
|
提示：
1 <= digits.length <= 9digits[i].length == 1digits[i] 是从 '1' 到 '9' 的数digits 中的所有值都 不同 digits 按 非递减顺序 排列1 <= n <= 10^9
思路：
数位DP，我们用is_limit来表示当前位数的数字是否受到限制，比如n = 123，若第一位已经填了数字1，则说明第二位数字只能填2, 3，也就是说被限制了。若第一位数字不填跳过，则第二位数字可以填0-9，也就是说并没有被限制。
用is_num来表示前一位是否填了数字，若前面没填数字，则表示该位也可以不填数字，因此可以构造出1位数字、2位数字…
为避免重复计算，我们设置数组dp，dp[i]表示在不受n限制的情况下，能写多少个(n.size() - i)位数字。
tip:
solve()返回从左往右第 i 位及其之后数位的合法方案数if(!is_limit && is_num && dp[i] >= 0)的原因是因为在代码顺序上，res是先将is_num == false的数量给加上了，再去计算剩余的，所以当is_num == true时，再返回dp[i]。并且is_limit == true时的情况只会出现一次，因此不需要记录。
代码如下：
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
| class Solution {
public:
vector<int> dp;
int solve(int i, string& n, vector<string>& digits, bool is_limit, bool is_num){
if(i == n.size())
return is_num;
if(!is_limit && is_num && dp[i] >= 0)
return dp[i];
int res = 0;
if(!is_num){
res += solve(i + 1, n, digits, false, false);
}
char up = (is_limit ? n[i] : '9');
for(auto& c : digits){
if(c[0] > up)
break;
res += solve(i + 1, n, digits, is_limit && c[0] == up, true);
}
if(!is_limit && is_num)
dp[i] = res;
return res;
}
int atMostNGivenDigitSet(vector<string>& digits, int n) {
string n_str = to_string(n);
dp.resize(n_str.size(), -1);
int res = solve(0, n_str, digits, true, false);
return res;
}
};
|
