企业官网建设流程全解析

这道题是一道典型的数位 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 cache

@cache
def 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 0

res = 0
# 如果没有开始填数字，当前位可以跳过（继续是前导0）
if 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 1

for d in range(start, up + 1):
# 计算新的奇偶差：奇数+1，偶数-1
new_diff = diff + (1 if d % 2 == 1 else -1)
# 计算新的余数：(当前余数 * 10 + 当前位数字) % k
new_mod = (mod * 10 + d) % k
# 递归进入下一位
res += dfs(i + 1, new_diff, new_mod, is_limit and d == up, True)

return res

return 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 编辑器中运行。如果有任何疑问，或者想了解其他语言的实现，随时告诉我！