902. 最大为 N 的数字组合 : 经典「数位 DP + 二分」运用题
题目描述
这是 LeetCode 上的 902. 最大为 N 的数字组合 ，难度为 困难。
Tag : 「动态规划」、「二分」、「数位 DP」
给定一个按 非递减顺序 排列的数字数组 digits。你可以用任意次数 digits[i]digits[i]digits[i] 来写的数字。例如，如果 digits=[1,3,5]digits = [1,3,5]digits=[1,3,5]，我们可以写数字，如 '13', '551', 和 '1351315'。
返回 可以生成的小于或等于给定整数 nnn 的正整数的个数 。
示例 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
提示：
- 1<=digits.length<=91 <= digits.length <= 91<=digits.length<=9
- digits[i].length==1digits[i].length == 1digits[i].length==1
- digits[i]digits[i]digits[i] 是从
'1'到'9'的数 digits中的所有值都 不同digits按 非递减顺序 排列- 1<=n<=1091 <= n <= 10^91<=n<=109
数位 DP + 二分
这是一道「数位 DP」的经典运用题。
由于题目给定的 digits 不包含 000，因此相当于只需要回答使用 digits 的数值能够覆盖 [1,x][1, x][1,x] 范围内的多少个数字。
起始先将字符串数组 digits 转为数字数组 nums，假定 nums 的长度为 mmm，然后考虑如何求得 [1,x][1, x][1,x] 范围内合法数字的个数。
假定我们存在函数 int dp(int x) 函数，能够返回区间 [1,x][1, x][1,x] 内合法数的个数，那么配合「容斥原理」我们便能够回答任意区间合法数的查询：
对于本题，查询区间的左端点固定为 111，同时 dp(0)=0dp(0) = 0dp(0)=0，因此答案为 dp(x)dp(x)dp(x)。
然后考虑如何实现 int dp(int x) 函数，我们将组成 [1,x][1, x][1,x] 的合法数分成三类：
- 位数和 xxx 相同，且最高位比 xxx 最高位要小的，这部分统计为
res1； - 位数和 xxx 相同，且最高位与 xxx 最高位相同的，这部分统计为
res2； - 位数比 xxx 少，这部分统计为
res3。
其中 res1 和 res3 求解相对简单，重点落在如何求解 res2 上。
对 xxx 进行「从高到低」的处理（假定 xxx 数位为 nnn），对于第 kkk 位而言（kkk 不为最高位），假设在 xxx 中第 kkk 位为 curcurcur，那么为了满足「大小限制」关系，我们只能在 [1,cur−1][1, cur - 1][1,cur−1] 范围内取数，同时为了满足「数字只能取自 nums」的限制，因此我们可以利用 nums 本身有序，对其进行二分，找到满足 nums[mid] <= cur 的最大下标 rrr，根据 nums[r]nums[r]nums[r] 与 curcurcur 的关系进行分情况讨论：
- nums[r]=curnums[r] = curnums[r]=cur: 此时位置 kkk 共有 rrr 种选择，而后面的每个位置由于 nums[i]nums[i]nums[i] 可以使用多次，每个位置都有 mmm 种选择，共有 n−pn - pn−p 个位置，因此该分支往后共有 r∗mn−pr * m^{n - p}r∗mn−p 种合法方案。且由于 nums[r]=curnums[r] = curnums[r]=cur，往后还有分支可决策（需要统计），因此需要继续处理；
- nums[r]<curnums[r] < curnums[r]<cur：此时算上 nums[r]nums[r]nums[r]，位置 kkk 共有 r+1r + 1r+1 种选择，而后面的每个位置由于 nums[i]nums[i]nums[i] 可以使用多次，每个位置都有 mmm 种选择，共有 n−pn - pn−p 个位置，因此该分支共有 (r+1)∗mn−p(r + 1) * m^{n - p}(r+1)∗mn−p 种合法方案，由于 nums[r]<curnums[r] < curnums[r]<cur，往后的方案数（均满足小于关系）已经在这次被统计完成，累加后进行
break； - nums[r]>curnums[r] > curnums[r]>cur：该分支往后不再满足「大小限制」要求，合法方案数为 000，直接
break。
其他细节：实际上，我们可以将 res1 和 res2 两种情况进行合并处理。
代码：
class Solution {
int[] nums;
int dp(int x) {
List<Integer> list = new ArrayList<>();
while (x != 0) {
list.add(x % 10);
x /= 10;
}
int n = list.size(), m = nums.length, ans = 0;
// 位数和 x 相同
for (int i = n - 1, p = 1; i >= 0; i--, p++) {
int cur = list.get(i);
int l = 0, r = m - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (nums[mid] <= cur) l = mid;
else r = mid - 1;
}
if (nums[r] > cur) {
break;
} else if (nums[r] == cur) {
ans += r * (int) Math.pow(m, (n - p));
if (i == 0) ans++;
} else if (nums[r] < cur) {
ans += (r + 1) * (int) Math.pow(m, (n - p));
break;
}
}
// 位数比 x 少的
for (int i = 1, last = 1; i < n; i++) {
int cur = last * m;
ans += cur; last = cur;
}
return ans;
}
public int atMostNGivenDigitSet(String[] digits, int max) {
int n = digits.length;
nums = new int[n];
for (int i = 0; i < n; i++) nums[i] = Integer.parseInt(digits[i]);
return dp(max);
}
}
- 时间复杂度：由于
digits最多存在 999 个元素，因此二分的复杂度可以忽略，整体复杂度为 O(logn)O(\log{n})O(logn) - 空间复杂度：O(C)O(C)O(C)
总结
数位 DP 的难度取决于「限制条件」的多少，而 LC 上仅有的几道数位 DP 题目限制条件都很少，且不需要引入额外的数据结构来记录状态，因此都属于数位 DP 的入门难度（LC 难度均为 Hard）。
几乎所有的数位 DP 问题都可以归纳到上述的解法 :「将问题抽象为求解一个 [0,x][0, x][0,x] / [1,x][1, x][1,x] 范围方案数的方法」->「对方案数统计根据 位数 来分情况讨论：数位相等的情况 + 数位不等情况」->「统计数位相等的方案数时，需要按位处理，并根据限制条件做逻辑；统计数位不等的方案数时，通常要做一些预处理，然后配合乘法原理直接算得」。
在还没卷到数位 DP 烂大街的现在，掌握此类求解方式单一，普遍定位为「困难」的数位 DP 类型，还是极具性价比的。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.902 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
转载自:https://juejin.cn/post/7155673730885091358