01先把问题说具体
统计 0 到 N 中各位数字之和恰好为 S 的整数个数。N 可以很大,不能逐个枚举。
02一步步得到方法
把枚举整数改成枚举位数选择
将 N 写成十进制数字数组。状态 (pos,total,tight) 表示处理到哪一位、已累积的数位和、前缀是否仍与 N 相同。tight=True 时本位最多选 N[pos],否则可选 0..9。
选 d 后,下一个 tight 是 tight and d==limit。只要前面已经严格小于上界,后续再选任何数字都不会超限;不能因为某一位恰好等于上界对应位就重新变成 tight。
前导零是否影响性质
本课允许在所有数字左侧补零到同样位数,数位和不受影响,因此无需额外 started 状态。数字 0 会被全零路径计一次。
若统计实际位数、数字 0 出现次数、相邻位是否相等,就需要 started 区分前导零与真正的数字位,或专门定义零的表示。每增加一种性质,都要判断需要在状态中保存什么信息。
把上界限制沿前缀传播
tight 表示当前前缀是否与上界相同。若已严格更小,后续位可自由取0到9;若仍相同,本位不能超过对应上界数字,且下一状态是否 tight 取决于本位是否相等。
前导零允许统一处理位数较短的数,但若性质涉及数字0出现次数、相邻数字或数的长度,必须加 started 等状态。特别是整数0本身,要单独决定是否计入及怎样表示。
03把一个小例子完全算清楚
N=25,目标数位和 S=3。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 十位选 0 | 已小于上界,个位可选 0..9 | 选个位 3,表示数字 3 |
| 十位选 1 | 仍小于上界 | 个位选 2,得到 12 |
| 十位选 2 | tight 保持,个位最多 5 | 选 1,得到 21 |
窄屏可左右滑动表格,阅读完整计算与理由。
满足条件的整数是 3、12、21,共 3 个;前导零不会制造重复数字。
04为什么这个方法成立
- 每个 0..N 整数对应唯一的等长补零数字序列。
- tight 约束确保构造前缀不超过 N,且所有合法数字选择都被枚举。
- 终点仅当数位和等于目标时计 1,缓存合并相同剩余子问题,不改变计数。
05把推导翻译成代码
Python · 可独立运行的教学实现
from functools import cache
def digit_sum_count(n, target):
if n < 0 or target < 0:
return 0
digits = list(map(int,str(n)))
@cache
def visit(pos,total,tight):
if total > target:
return 0
if pos == len(digits):
return int(total == target)
limit = digits[pos] if tight else 9
return sum(visit(pos+1,total+d,tight and d==limit)
for d in range(limit+1))
return visit(0,0,True)逐个理解关键决定
tight and d==limit- 只有之前仍贴上界且本位也取上界,下一状态才继续受限。
total > target- 数位非负,后续无法把和降回目标,因此可安全剪枝。
06时间、空间与实现范围
位数 D、目标和 S,有 O(D·S) 个主要缓存状态,每个枚举最多 10 个数字;空间 O(D·S) 加递归 O(D)。
大整数计数和字符串位数成本需按实际规模考虑;范围 [L,R] 可用 F(R)−F(L−1)。
07改变条件,检查哪里会出错
把每个补零都算成数字 0 出现
会错误统计较短整数;对这种性质增加 started 状态。
在不同上界之间直接复用依赖上界的缓存
若缓存键未包含上界或相关限制,换查询后可能读到旧结果;应清缓存或设计可复用状态。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
0 到 0,数位和 0 有几个?
需要一点提示
包含数字 0 本身。
查看解析与答案
1 个。
统计 10..25 中和为 3 的个数?
需要一点提示
减去 0..9。
查看解析与答案
F(25)−F(9)=3−1=2,对应 12、21。
统计不含相邻相同数字需新增什么状态?
需要一点提示
判断当前位需要知道什么过去信息?
查看解析与答案
上一真实数字 last,以及是否已经开始 started;前导零不能当普通前一位。