最大为 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.

示例 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 <= 9
digits[i].length == 1
digits[i] 是从 '1' 到 '9' 的数
digits 中的所有值都不同
digits 按 非递减顺序 排列
1 <= n <= 10⁹

Submission

运行时间: 24 ms

内存: 16.0 MB

class Solution:
    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
        S = str(n)
        K = len(S)

        dp = [0] * K + [1]
        # dp[i] 表示比S[i:]小的选法

        # 位数比n小的可以随便取，位数和n相同的，有比较的取，用dp
        for i in range(K-1, -1, -1):
            for d in digits:
                if d < S[i]:
                    dp[i] += len(digits) ** (K-1-i)
                if d == S[i]:
                    dp[i] += dp[i+1]
        return dp[0] + sum([len(digits) ** j for j in range(1, K)])

Explain

这个解法使用动态规划来计算能生成的小于或等于n的数字的个数。首先，将n转换为字符串S以便逐位比较。创建一个dp数组，其中dp[i]表示使用digits中的数字，生成的数字小于S的第i位到最后一位的子字符串。遍历每一位数字，比较digits中的每个元素与S的当前位。如果digit小于S的当前位，则可以自由地选择剩余的位，其个数是len(digits)的(K-i-1)次幂。如果digit等于S的当前位，则当前位固定，剩余位的选择数等于dp[i+1]。最终，dp[0]加上所有小于K位数的组合数给出答案。

时间复杂度: O(K * len(digits))

空间复杂度: O(K)

class Solution:
    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
        S = str(n)  # 将整数n转换为字符串
        K = len(S)  # 获取n的位数

        dp = [0] * K + [1]  # 初始化dp数组，长度为K+1，dp[K]初始化为1表示空集

        # 遍历n的每一位，从最低位到最高位
        for i in range(K-1, -1, -1):
            # 遍历digits中的每个数字
            for d in digits:
                if d < S[i]:  # 如果digit小于当前位
                    dp[i] += len(digits) ** (K-1-i)  # 可以选择剩下的所有位
                if d == S[i]:  # 如果digit等于当前位
                    dp[i] += dp[i+1]  # 继承下一位的可能性
        # 计算所有位数少于K的组合数总和
        return dp[0] + sum([len(digits) ** j for j in range(1, K)])

Explore

在这个解法中，dp数组用于存储从某一位开始到数字n的末尾所能组成的数字数量。dp[K]初始化为1的原因是它代表了一个边界条件，即当我们考虑的数字长度正好等于n的长度时，之后不再有数字可以添加。在这种情况下，dp[K]作为一个加法单位（即加0的效果）被使用，它代表了末尾没有更多数字可以添加的情况。因此，当我们在计算比较时，如果digit等于S的最后一位，我们会将dp[K]（即1）加入计算，表示这种匹配情况确实存在一种可能。

当digit小于当前位S[i]时，意味着无论在这一位之后的位数选择什么数字，组成的数都会小于n。在这种情况下，我们可以自由地为所有剩余的位选择digits中的任何数字。这里的逻辑是基于这样一个事实：由于当前位已经保证了比n的相应位小，因此后面的位无论如何填充，构成的数字都不会超过n。例如，如果n是234，当前位我们选择了1（假设digit中有1），那么后续位无论是00、01、99等，组成的数（100、101、199等）都不会超过234。

当digit等于S[i]时，意味着当前位数与n在这一位上完全相同，因此我们不能自由选择任何更大的数字，而必须依赖于下一位的数字组合来确保不超过n。dp[i+1]存储的是从下一位开始的所有可能的数字组合数。通过添加dp[i+1]，我们实际上是将这一位固定在与n相同的数字，然后考虑所有由后续位构成的可能数字。因此，这种方法确实考虑了所有在保证当前位数与n相同的情况下，由更小的位数组合可能产生的所有数字。