这道题是一道典型的数位 DP动态规划问题。题目分析我们需要统计在 [low, high] 范围内满足以下两个条件的“美丽整数”的个数1. 偶数数位的数目与奇数数位的数目相同。2. 这个整数可以被 k 整除。解题思路数位 DP 的经典套路是将区间问题转化为前缀和问题f(high) - f(low - 1)即计算 [0, high] 中的美丽整数个数减去 [0, low-1] 中的美丽整数个数。在记忆化搜索DFS的过程中我们需要关注以下几个核心状态1. 当前位数 i表示正在处理字符串的第几位。2. 奇偶数位差 diff记录当前已填数字中奇数个数减去偶数个数的差值。最终要求 diff 0。3. 当前余数 mod记录当前已填数字对 k 取模的结果。最终要求 mod 0。4. 是否受限 is_limit表示前面填的数字是否都和上限 high或 low-1的对应位相同。如果是当前位最大只能填上限的当前位数字否则可以填 0-9。5. 是否已开始填数 is_num用于处理前导零。因为前导零不应该被算作偶数位只有真正开始填非零数字后奇偶统计才开始生效。Python3 代码实现class Solution:def numberOfBeautifulIntegers(self, low: int, high: int, k: int) - int:# 计算 [0, n] 范围内美丽整数的个数def count_beautiful(n: int) - int:s str(n)length len(s)# 使用缓存装饰器进行记忆化搜索from functools import cachecachedef dfs(i: int, diff: int, mod: int, is_limit: bool, is_num: bool) - int:# 递归边界填完所有位数if i length:# 必须填了数字且奇偶数位差为0且能被k整除return 1 if is_num and diff 0 and mod 0 else 0res 0# 如果没有开始填数字当前位可以跳过继续是前导0if not is_num:res dfs(i 1, diff, mod, False, False)# 确定当前位可以填的数字上限up int(s[i]) if is_limit else 9# 确定当前位可以填的数字下限如果还没开始填不能填0要从1开始否则可以从0开始start 0 if is_num else 1for d in range(start, up 1):# 计算新的奇偶差奇数1偶数-1new_diff diff (1 if d % 2 1 else -1)# 计算新的余数(当前余数 * 10 当前位数字) % knew_mod (mod * 10 d) % k# 递归进入下一位res dfs(i 1, new_diff, new_mod, is_limit and d up, True)return resreturn dfs(0, 0, 0, True, False)return count_beautiful(high) - count_beautiful(low - 1)复杂度分析* 时间复杂度O(log high times k times log high)。状态总数由位数log high、奇偶差范围在 [-log high, log high]和余数k决定。* 空间复杂度O(log high times k times log high)主要用于记忆化搜索的缓存空间。你可以直接将这段代码复制到 LeetCode 编辑器中运行。如果有任何疑问或者想了解其他语言的实现随时告诉我