千问 LeetCode 2719. 统计整数数目 Python3实现
这道题是经典的数位动态规划（Digit DP）问题。由于数字范围极大（可达 10^{22}），直接暴力遍历会超时，因此我们需要使用记忆化搜索来高效解决。
💡 核心思路
1. 前缀和思想（转化为 0 到 N 的问题）：
题目要求计算区间 [num1, num2] 内的合法整数个数。我们可以将其转化为求 calc(num2) - calc(num1 - 1)。即：先算出 0 到 num2 的合法个数，再减去 0 到 num1-1 的合法个数。
2. 记忆化搜索（DFS + Memoization）：
从最高位开始，一位一位地确定数字。在搜索过程中记录以下状态：
* pos：当前处理到第几位。
* digit_sum：当前已经确定的各位数字之和。
* is_limit：当前位是否受到上界字符串的限制。如果前面的位都填了上界的对应数字，当前位最大只能填上界的当前位数字；否则可以填 0-9。
3. 剪枝与边界处理：
* 如果当前的 digit_sum 已经超过了 max_sum，直接返回 0。
* 当遍历完所有位数时，检查 digit_sum 是否大于等于 min_sum，满足则返回 1，否则返回 0。
* 由于 num1 是字符串，计算 num1 - 1 需要手写一个字符串减法（高精度减一）。
💻 Python3 实现代码
class Solution:
MOD = 10**9 + 7
def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
self.min_sum = min_sum
self.max_sum = max_sum
# 结果是 calc(num2) - calc(num1 - 1)
# 为了避免负数，先加上 MOD 再取模
return (self.calc(num2) - self.calc(self.subtract_one(num1)) + self.MOD) % self.MOD
# 计算从 0 到字符串 num 范围内，满足数位和条件的整数个数
def calc(self, num: str) -> int:
n = len(num)
# 记忆化数组：memo[i][j] 表示处理到第 i 位，当前数位和为 j 时的方案数
# 数位和最大为 9 * 22 = 198，但题目 max_sum 最大为 400，取较小值优化空间
memo = [[-1] * (min(9 * n, self.max_sum) + 1) for _ in range(n)]
# 深度优先搜索（使用闭包方便调用 memo 和 num）
def dfs(pos: int, digit_sum: int, is_limit: bool) -> int:
# 剪枝：如果当前和已经超过最大值，后面的位无论填什么都不合法
if digit_sum > self.max_sum:
return 0
# 递归终点：所有位都填完了
if pos == n:
# 检查数位和是否满足最小值要求
return 1 if digit_sum >= self.min_sum else 0
# 如果当前状态不受限制，且已经计算过，直接返回缓存结果
if not is_limit and memo[pos][digit_sum] != -1:
return memo[pos][digit_sum]
res = 0
# 确定当前位能填的最大数字
up = int(num[pos]) if is_limit else 9
# 枚举当前位可以填的数字 (0 到 up)
for d in range(up + 1):
# 如果当前位填了最大值 up，且之前受限制，那么下一位继续受限制；否则下一位不受限制
res = (res + dfs(pos + 1, digit_sum + d, is_limit and d == up)) % self.MOD
# 只有不受限制的状态才能被缓存（受限制的状态只会出现一次，缓存没有意义）
if not is_limit:
memo[pos][digit_sum] = res
return res
# 从第 0 位开始，当前数位和为 0，受到上界限制
return dfs(0, 0, True)
# 字符串高精度减一（用于计算 num1 - 1）
def subtract_one(self, num: str) -> str:
chars = list(num)
i = len(chars) - 1
# 从最后一位开始借位
while chars[i] == '0':
chars[i] = '9'
i -= 1
chars[i] = str(int(chars[i]) - 1)
# 将列表转回字符串
result = ''.join(chars)
# 如果减完首位变成0（例如 "100" -> "099"），需要去掉前导零
return result[1:] if result[0] == '0' and len(result) > 1 else result
📊 复杂度分析
* 时间复杂度：O(L * S * 10)。其中 L 是数字字符串的最大长度（最多 22 位），S 是 max_sum（最多 400）。对于每一位，我们最多枚举 0-9 这 10 个数字，且通过记忆化避免了重复计算。
* 空间复杂度：O(L * S)。主要用于 memo 记忆化数组以及递归调用的栈空间。