Kimi LeetCode 3906. 统计网格路径中好整数的数目 Python3实现

根据搜索结果LeetCode 3906「统计网格路径中好整数的数目」的 Python3 实现如下---思路1. 预处理关键位置directions 包含 3 个 D 和 3 个 R从 (0,0) 出发共经过 7 个格子含起点。将这些格子在 16 位字符串中的位置标记为 key[i] true。2. 数位 DP统计 [0, x] 范围内满足条件的数字个数答案为 calc(r) - calc(l-1)。3. 状态定义dfs(pos, last, lim)- pos当前处理到第几位015- last路径上上一个关键位置的数字- lim是否受上界限制4. 转移如果当前位置是关键位置则该位数字必须 last并更新 last否则该位可取任意数字09last 不变。---Python3 实现pythonfrom functools import cacheclass Solution:def countGoodIntegersOnPath(self, l: int, r: int, directions: str) - int:# 预处理标记路径上的关键位置key [False] * 16row, col 0, 0key[0] True # 起点 (0,0)for c in directions:if c D:row 1else:col 1key[row * 4 col] Trues cachedef dfs(pos: int, last: int, lim: bool) - int:# 所有 16 位处理完毕if pos 16:return 1res 0# 关键位置数字不能小于上一个关键位置的数字start last if key[pos] else 0# 受限制时上界为 s[pos]end int(s[pos]) if lim else 9for i in range(start, end 1):# 当前是关键位置则更新 last否则保持next_last i if key[pos] else last# 继续受限的条件当前已受限且选到了上界next_lim lim and (i end)res dfs(pos 1, next_last, next_lim)return resdef calc(x: int) - int:nonlocal sif x 0:return 0# 补前导零至 16 位s str(x).zfill(16)# 每次计算前清空缓存dfs.cache_clear()return dfs(0, 0, True)return calc(r) - calc(l - 1)---复杂度- 时间复杂度O(D^2 \times \log r)其中 D 10 为数字范围\log r 16 为位数。- 空间复杂度O(D \times \log r) O(160)记忆化缓存大小。