企业官网建设流程全解析

一、为什么"数数字"这种题也配叫 DP

先看一道看起来人畜无害的题：统计 [1, n] 中数字 1 一共出现了多少次（LeetCode 233）。

比如 n = 13，答案是 6：

1 -> 1 个 1 10 -> 1 个 1 11 -> 2 个 1 12 -> 1 个 1 13 -> 1 个 1 合计: 1+1+2+1+1 = 6

第一反应肯定是暴力：从 1 循环到 n，每个数逐位数 1，累加。n 小的时候完全没问题。但题目里 n 可以大到 10⁹，你循环 10 亿次，直接超时。

这里就暴露出数位 DP 要解决的根本问题：当"数"本身大到无法枚举每个整数时，我们枚举它的"数位"。

一个数无非是一串数字。比如 123 就是[1,2,3]。我们不关心它"是哪个数"，只关心"它每一位填了什么"。于是问题从"遍历 1~n 这 n 个数"，变成"从高位到低位，一位一位地填数字，每一位能填什么由约束决定"——这正是一个标准的"逐阶段决策 + 状态转移"的 DP 问题。

二、数位 DP 三要素：pos / tight / 附加状态

任何一道数位 DP 题，dfs 的状态永远由下面三类信息构成。

2.1 pos：当前填到第几位

把 n 转成字符串s，比如n = 23则s = "23"，从下标 0（最高位）一路填到最后一位。pos就表示"现在正在决定 s[pos] 这位填几"。

2.2 tight：是否还贴着上界（最关键的状态）

这是数位 DP 的灵魂。假设 n = 23，现在已经填了十位 = 2（和 n 的十位一样），那个位就不能随便填了——它最多只能填到 3，否则就超过 23 了。

反之，如果十位填的是 1（比 n 的十位小），那位个位想填 0~9 随便填，怎么都不会超过 23。

tight就是记录这个"是否还贴着上界"的布尔量：

limit = int(s[pos]) if tight else 9 # 循环枚举 d = 0 .. limit # 下一位是否继续贴上界： next_tight = tight and (d == limit)

一旦某一位填得比上界小，tight就永久变成False，后面所有位都放开了。

2.3 附加状态：随题目变化

前两个是通用的。第三个状态看你这题要统计/约束什么：

• 233 题要统计"1 出现了多少次"，所以要带一个cnt状态，记录到目前为止已经选了几个 1，走到末尾就把 cnt 累加进答案。

• 600 题要求"不能有连续两个 1"，所以要带一个prev1状态，记录上一位是不是 1。如果上一位是 1，本位就禁止再填 1。

2.4 一个容易踩的坑：记忆化只缓存 tight=False

dfs 用@lru_cache记忆化。注意：tight=True的状态在整个搜索树里其实只出现一条路径（就是严格等于 n 本身那条），它没有重复利用价值，缓存了也只命中一次；真正会被大量重复访问的是tight=False的子树。

所以如果你把 tight 也写进缓存键里也没问题（只是缓存稍大），但理解"tight 决定了状态是否唯一"，你就懂了为什么模板这么写不会重复计算。

下面这张图把整个搜索决策过程画出来：

三、实战一：LeetCode 233 整数中1出现的次数

状态设计：dfs(pos, tight, cnt)，cnt是到目前为止已经出现的 1 的个数。走到末尾时返回cnt（把这条路径上的 1 个数贡献出去）。

from functools import lru_cache def countDigitOne(n: int) -> int: s = str(n) @lru_cache(maxsize=None) def dfs(pos: int, tight: bool, cnt: int) -> int: # pos: 当前位；tight: 是否贴上界；cnt: 已出现的1的个数 if pos == len(s): return cnt # 走到尽头，返回这一整串数字里 1 的总数 limit = int(s[pos]) if tight else 9 res = 0 for d in range(limit + 1): # 选了数字 d，它贡献 1 个"1"当且仅当 d == 1 res += dfs(pos + 1, tight and d == limit, cnt + (1 if d == 1 else 0)) return res return dfs(0, True, 0)

本地运行验证（Python 3，真实输出）

=== LeetCode 233 整数中1出现的次数 === countDigitOne(13) = 6 countDigitOne(0) = 0 countDigitOne(1) = 1 countDigitOne(9) = 1 countDigitOne(99) = 20 countDigitOne(100) = 21 countDigitOne(1000)= 301

对照 LeetCode 官方样例：n=13 → 6✓，n=0 → 0✓。其余几个我也手算了：1~99 里 1 出现在个位 10 次 + 十位 10 次 = 20 ✓；1~100 多了 100 里的那个百位 1，20+1=21 ✓。完全对上。

复杂度：状态数是位数 × 2 × (位数)，n 是 10 位数时状态也就几千个，每个状态枚举 10 个数字，整体 O(位数² × 10)，对 10⁹ 瞬间出结果，暴力法想都不敢想。

四、实战二：LeetCode 600 不含连续1的非负整数

这题换个角度：我们按二进制来看 n。要求是 [0, n] 里，二进制表示不能出现相邻两个 1的数有多少个。

状态设计：dfs(pos, tight, prev1)。prev1记录上一位是不是 1。如果prev1 == True，那本位只能填 0（填 1 就连续了）。

def findIntegers(n: int) -> int: s = bin(n)[2:] # 转二进制字符串，比如 5 -> "101" @lru_cache(maxsize=None) def dfs(pos: int, tight: bool, prev1: bool) -> int: if pos == len(s): return 1 # 走到尽头，这条合法路径计 1 个数 limit = int(s[pos]) if tight else 1 # 二进制每位只能是 0/1 res = 0 for d in range(limit + 1): if d == 1 and prev1: continue # 上一位已经是1，本位不能再填1 res += dfs(pos + 1, tight and d == limit, d == 1) # 本位选了1，传给下一位 return res return dfs(0, True, False)

本地运行验证（Python 3，真实输出）

=== LeetCode 600 不含连续1的非负整数 === findIntegers(5) = 5 findIntegers(1) = 2 findIntegers(2) = 3 findIntegers(10) = 8 findIntegers(20) = 12 findIntegers(100)= 34

对照官方样例：n=5 → 5（0,1,10,100,101）✓，n=1 → 2（0,1）✓。

五、两题对比，看透模板

对比着看你会发现：dfs 骨架一模一样，变的只有两件事——附加状态是什么、以及走到末尾返回什么。这就是数位 DP 的可迁移性。

六、常见坑与迁移路线

坑1：要不要is_num状态？有些题（比如"不含前导零"）需要知道前面到底有没有开始填非零数字，这时要加is_num。但 233 和 600 都不涉及"前导零算不算"的问题——233 从 1 开始数 1（0 不贡献），600 把 0 也算一个合法数，所以两题都不需要is_num。别一上来就套全套模板，按需加状态。

坑2：二进制题别忘bin(n)[2:]。600 这种题先把 n 转成二进制串再做，否则按十进制做就南辕北辙了。

坑3：记忆化顺序。tight=True的分支不要依赖被缓存的结果去覆盖——因为我们缓存的是tight=False的通用子树，tight=True路径每次唯一计算，互不干扰。

迁移路线：把这套模板背下来，后面这些题都是换个附加状态：

• LeetCode 1012「至少有一位重复的数字」：附加状态是"已用过的数字集合"（位掩码）。

• LeetCode 902「最大为 N 的数字组合」：附加状态无额外约束，纯计数。

• LeetCode 1015「可被 K 整除的最小整数」：附加状态是"当前余数 mod K"。

七、小结

数位 DP 看着唬人，本质就三句话：

1. 把数拆成数字串，从高位到低位一位一位填；

2. 用tight判断本位能填到几，做上界剪枝；

3. 题目关心什么，就加什么附加状态，dfs 末尾把贡献返回。

掌握这套模板后，你会发现一大片 hard 难度的"按位统计/数位约束"题，其实都是同一个模子刻出来的。

参考资料

1. LeetCode 233. Number of Digit One — https://leetcode.com/problems/number-of-digit-one/

2. LeetCode 600. Non-negative Integers without Consecutive Ones — https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/

3. 数位 DP 通用模板（记忆化搜索）——竞赛算法笔记