Leecode902.最大为 N 的数字组合（hard）

题目简述链接

给定一个按非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如，如果 digits = [‘1’,‘3’,‘5’]，我们可以写数字，如 ‘13’, ‘551’, 和 ‘1351315’。
返回 可以生成的小于或等于给定整数 n 的正整数的个数 。

相关示例

实例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.
1
2
3
4
5

实例2

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

实例3

输入：digits = ["7"], n = 8
输出：1
1
2

输入的相关说明

提示：

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

解题思路

思路一：基于前向比较的算法

就比如说拿题目中的实例：

digits = ["1","3","5","7"], n = 100
1

我们可以将其分为两个部分第一部分是我们使用数字n的一个数字和后面的数字，第二部分就是我们完全不适用第一位数字那么n中还有2个位置所以第二部分共有$4^2+4^1=20$个不同的组合。接下来我们分析第一部分的数字，在这里记$n[i]$为数字n位置$i$上的数字。
之后我们将$digits$里面的数字与之相比较，如果某个$d$小于$n[i]$的话，那么此时位置$i$后面的字符可以随意的从$digits$中选取并且产生的结果仍然不会超过数字n。另外如果对于某个数字$d==n[i]$那么我们便需要向前挪动一位再次与$digits$里面的数字比较。而如果$n[i]$超过其中的一个$d$那么我们便可以返回了，因为此位置往后不可能产生比n小的数字。下面是图示

class Solution:
    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
        s_n = str(n)
        l = len(s_n)
        res = sum([len(digits)**i for i in range(1, l)])
        for i,s in enumerate(s_n):
            flag_eq = False
            for d in digits:
                if d < s:
                    res += len(digits)**(l-i-1)
                else:
                    if d == s:
                        flag_eq = True
                        break
            if not flag_eq:
                return res
        return res+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

思路二：数位DP

对于数位DP来说，由于题主在写这道题目的时候没有想到所以就借用官方的解决方法来给大家介绍一下：
设 n 是一个十进制的 k位数，所有数字位数小于 k 且由 $\text{digits}$ 组成的数字则一定是小于 nn 的。我们用 $\text{dp}[i][0]$ 表示由 $\text{digits}$ 构成且n 的前 i位的数字的个数，$dp[i][1]$表示由 \textit{digits}digits 构成且等于 nn 的前 ii 位的数字的个数，可知 $dp[i][1]$ 的取值只能为 0 和 1,因为不可能出现其他的情况只能相等或者不相等。

例如：$n=2345,\text{digits}=\text{[“1",“2",“3",“4"]}n=2345,digits=[“1",“2",“3",“4"]。$

则$dp[1][0],dp[2][0],dp[3][0],dp[4][0]$分别表示小于$2,23,234,2345$的合法数的个数，$dp[1][1],dp[2][1],dp[3][1],dp[4][1]$ 分别表示等于$2,23,234,2345$的合法数的个数。

设 $\text{digits}$中的字符数目为 m个，数字 n的前 j 位构成的数字为 $\text{num}[j]$，数字 n 的第 jj 个字符为 $s[j]$，当遍历到 n 的第i 位时：

当满足 $i>1$ 时，此时任意数字d构成的数字一定满足$d<\text{num}[i]$

设数字 $a<\text{num}[i-1]$，则此时在a的末尾追加一个数字d构成的数为$a\times 10+d$，此时可以知道d取$0,1,\cdots ,9$中任意数字均满足小于$a\times 10+d<\text{num}[i]=\text{num}[i-1]\times 10+s[i]$；

设数字$a=\text{num}[i-1]$，则此时在$a$的末尾追加一个数字$d$构成的数为$a\times 10+d$，此时可以知道$d<s[i]$时，才能满足$a\times 10+d<\text{num}[i]=\text{num}[i-1]\times 10+s[i]$；

初始化时令$\text{dp}[0][1]=1$，如果前 $i$中存在某一位 $j$，对于任意数字$d$均不能满足$d=s[j]$，则此时$\text{dp}[i][1]=0$；

根据上述描述从小到到计算 $dp$，设 $C[i]$ 表示数组$\text{digits}$中小于n的第 $i$位数字的元素个数，则状态转移方程为：
$$dp[i][0]=\{\begin{array}{ll}C[i],& i=1\\ m+dp[i-1][0]\times m+dp[i-1][1]\times C[i],& i>1\end{array}$$

我们计算出前 $k$ 位小于$n$的数字的个数$\text{dp}[k][0]$，前$k$位等于$n$的数字的个数 $\text{dp}[k][1]$，最终的答案为 $\text{dp}[k][0]+\text{dp}[k][1]$。

class Solution:
    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
        m = len(digits) #计算digits的长度
        s = str(n)
        k = len(s)
        dp = [[0, 0] for _ in range(k + 1)] #初始化dp矩阵
        dp[0][1] = 1   #由于数字n的前0位数字是空所以设置为1
        for i in range(1, k + 1):
            for d in digits:
            	#更新dp[i][1]的状态，如果s[i-1]存在于digits中则让其等于前面的dp[i-1][1]
                if d == s[i - 1]:
                    dp[i][1] = dp[i - 1][1]
                elif d < s[i - 1]:
                #如果小于的话那么我们加上前i-1位置上相等的序列，此时还是小于
                    dp[i][0] += dp[i - 1][1]
                else:
                    break
            #如果i>1的话才可以使用下面的式子进行更新，由于dp[i-1][0]是小于所以可以任意接digits
            #再加上现在的序列可以不使用前i-1个位置，用0代替，那么仍然可以使用digits放在该位置
            #使其小于n
            if i > 1:
                dp[i][0] += m + dp[i - 1][0] * m
        return sum(dp[k])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

思路三：递归

递归的思想和思路一的前向计算有着异曲同工的地方，有兴趣的读者也已继续阅读一下。

class Solution:
    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
        s_n = str(n)
        l_d = len(digits)
        l = len(s_n)
        def recusive(s):
            if s == "":
                return 1
            cnt, flag_eq, = 0, False
            for d in digits:
                if d < s[0]:
                    cnt += 1
                else:
                    if d == s[0]:
                        flag_eq = True
                        break
            if flag_eq:
                r = recusive(s[1:])
            else:
                r = 0
            return cnt * (l_d**(len(s)-1)) + r    
        return recusive(s_n) + sum([l_d**i for i in range(1, l)])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22