这题是数位 dp 类型的题，遍历对象有两个：
- 遍历 N 的每一位
- 遍历 digits
问题规模是 N 的位数。
状态转移方程是这样思考得出：
在遍历 digits 时，设当前 digits 的值为 digits[i]：
- 如果 digits[i]比 N 的第 j 位的数字小，则低位的数字就可以任意，那么由 digits[i]开头所产生的组合数是：
digits.length**(j-1)。
- 如果 digits[i]等于 N 的第 j 位数字，则还要继续对比第 j-1 位才知道能否凑出一个比 N 小的，也即递归，缩小问题规模。产生组合：dp[j-1]
- 如果 digits[i]大于 N 的第 j 位数字，则后面低位的数字不管是什么，都已经不能产生小于 N 的组合了。产生组合：0
把每个 digits[i]对应的结果加起来，就是当前问题规模（问题规模为：j）的答案。
状态转移方程：
1
2
3
4
5
| if (digits[i] < N[j]) {
dp[j] += digits.length ** (j - 1);
} else if (digits[i] == N[j]) {
dp[j] += dp[j - 1];
}
|
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| function atMostNGivenDigitSet(digits: string[], n: number): number {
const nStr = n.toString();
const dp = new Array(nStr.length).fill(0);
const memo = [];
for (let i = 1, res = 1; i < nStr.length; i++) {
memo.push((res = res * digits.length));
}
for (let i = 0; i < nStr.length; i++) {
for (let j = 0; j < digits.length; j++) {
if (digits[j] < nStr[nStr.length - 1 - i]) {
dp[i] += i > 0 ? memo[i - 1] : 1;
} else if (digits[j] == nStr[nStr.length - 1 - i]) {
console.log(digits[j], nStr[nStr.length - 1 - i], dp);
dp[i] += i > 0 ? dp[i - 1] : 1;
}
}
}
return memo.reduce((a, b) => a + b, 0) + dp[dp.length - 1];
}
|