如何用Python3实现LeetCode 902题的最大为N的数字组合算法？

题目链接：902 最大为 N 的数字组合 目录1. 题目解读2. 核心解题思路3. 解法一：数学排列组合法（推荐）【⭐】代码实现复杂度分析4. 解法二：数位动态规划 (Digit DP)代码实现复杂度分析5. 总结与对比 1. 题目解读 题目大意： 给定一个允许使用的数字集合 digits（例如 ['1', '3', '5']），你可以使用这些数字任意次来组成新的正整数。 现在给定一个上限整数 n，请问能组成多少个 小于或等于 n 的正整数？ 关键点： 数字可重复使用：这暗示了这是一个排列组合问题，或者可以使用动态规划。 上限限制：组成的数字必须 \(\le n\)。 无前导零：题目中 digits 只包含 '1' 到 '9'，所以不需要考虑 '0' 作为前导的问题，组成的数字天然合法。 示例分析： digits = ["1","3","5","7"], n = 100 一位数：1, 3, 5, 7 (共 4 个) 两位数：11, 13, ..., 77 (共 \(4 \times 4 = 16\) 个) 三位数：必须 \(\le 100\)。由于最小能组成的三位数是 111，已经大于 100，所以三位数个数为 0。 总计：\(4 + 16 = 20\)。 2. 核心解题思路 我们可以将问题拆分为两部分来统计： 位数少于 n 的数字： 假设 n 有 \(L\) 位。任何位数 \(k < L\) 的数字，只要由 digits 组成，一定小于 n。 对于长度为 \(k\) 的数字，每一位都有 len(digits) 种选择。 所以长度为 \(k\) 的数字共有 len(digits)^k 个。 我们需要累加 \(k = 1\) 到 \(L-1\) 的所有情况。 位数等于 n 的数字： 这部分比较麻烦，因为必须满足 \(\le n\) 的限制。 我们需要从高位到低位（从左到右）逐位确定数字。 假设 n 的字符串形式为 \(S\)。 在第 \(i\) 位时，我们尝试从 digits 中选一个数字 \(d\)： 情况 A：\(d < S[i]\) 如果当前位选的数字比 n 的对应位小，那么后面的所有位可以任意选择 digits 中的数字。 假设后面还有 \(rem\) 位，则有 len(digits)^rem 种组合。 统计完这些后，当前位选更小的数字的情况就全部算完了。 情况 B：\(d == S[i]\) 如果当前位选的数字和 n 的对应位相等，那么这一位暂时符合限制，但我们需要继续检查下一位（因为整体大小还没确定）。 我们不能直接计算后面的组合数，必须进入下一轮循环。 情况 C：\(d > S[i]\) 如果当前位选的数字比 n 的对应位大，那么组成的数字一定大于 n，不合法。 由于 digits 是排序好的，后面的数字也会更大，可以直接停止当前位的遍历。 特殊情况：如果我们可以一路匹配到最后一位（即 n 本身也可以由 digits 组成），那么 n 本身也是一个合法数字，需要额外 +1。 3. 解法一：数学排列组合法（推荐）【⭐】 这是最直接、效率最高的方法。利用上述思路，通过循环逐位计算。