1. 从具体问题到通用模型：理解数字计数的本质
遇到"统计N位数中偶数个3的个数"这类问题时，很多初学者会陷入暴力枚举的思维陷阱。我刚开始刷题时也犯过这个错误——试图手动列出所有两位数来验证样例。这种方法的局限性在N=1000时就会暴露无遗：宇宙中所有原子加起来都不够存储这个量级的数据。
更聪明的做法是观察数字生成的模式规律。想象你正在用打印机逐位生成数字：当打印第i位时，当前数字包含3的奇偶性只取决于两个因素：前i-1位中3的数量奇偶性，以及第i位是否选择打印3。这就是状态转移的雏形——把复杂问题分解为阶段决策过程。
举个例子，当N=2时：
- 前驱状态是1位数（0-9）
- 偶状态（0个3）：数字0,1,2,4,5,6,7,8,9
- 奇状态（1个3）：数字3
- 转移规则：
- 偶状态 + 非3 → 新偶状态（如1→12）
- 偶状态 + 3 → 新奇状态（如1→13）
- 奇状态 + 非3 → 新奇状态（如3→34）
- 奇状态 + 3 → 新偶状态（如3→33）
这种思考方式将问题转化为状态机模型，每个数字的生成过程就像在状态之间跳转的路径。通过记录到达每个状态的路径数量，我们就能避免重复计算，这正是动态规划的核心思想。
2. 构建递推公式：状态转移的数学表达
理解了状态概念后，我们需要用数学语言精确描述转移过程。定义两个关键变量：
- a[i]：i位数中偶数个3的数量
- b[i]：i位数中奇数个3的数量
对于非最高位的情况（i < N），转移方程非常直观：
a[i] = a[i-1] × 9 + b[i-1] × 1 b[i] = a[i-1] × 1 + b[i-1] × 9解释这个公式时，可以想象在已有的i-1位数前插入一个新数字：
- 第一项a[i-1]×9：原偶数个3的情况下，新增数字选择非3（1-9共9个选择）
- 第二项b[i-1]×1：原奇数个3的情况下，新增数字选择3（仅1个选择）
但这里有个边界陷阱需要特别注意：当处理最高位时（i=N），数字不能以0开头。因此转移系数需要调整：
- 非3的选择从9种（1-9）降为8种（排除0和3）
- 其他转移规则保持不变
用表格对比两种情况更清晰：
| 位数情况 | 转移来源 | 可选数字 | 系数变化 |
|---|---|---|---|
| i < N | 偶状态→偶状态 | 0-9除3 | ×9 → ×9 |
| 奇状态→偶状态 | 3 | ×1 → ×1 | |
| i = N | 偶状态→偶状态 | 1-9除3 | ×9 → ×8 |
| 奇状态→偶状态 | 3 | ×1 → ×1 |
这个细微差别正是很多同学首次实现时出错的地方。我在一次周赛中就因此WA了三次，最后通过对比N=2和N=3的手算结果才发现问题所在。
3. 动态规划的实现技巧
将理论转化为代码时，有几个实战要点需要特别注意。先看优化后的AC代码核心部分：
const int MOD = 12345; int a[MAXN], b[MAXN]; void solve(int N) { a[1] = 9; // 1-9 b[1] = 1; // 3 for(int i=2; i<=N; i++) { int choices = (i == N) ? 8 : 9; a[i] = (a[i-1]*choices + b[i-1]*1) % MOD; b[i] = (a[i-1]*1 + b[i-1]*choices) % MOD; } }空间优化技巧：当N很大时（比如1e6），可以改用滚动数组节省空间：
int a_prev = 9, b_prev = 1; for(int i=2; i<=N; i++) { int choices = (i == N) ? 8 : 9; int a_curr = (a_prev*choices + b_prev*1) % MOD; int b_curr = (a_prev*1 + b_prev*choices) % MOD; a_prev = a_curr; b_prev = b_curr; }常见坑点排查：
- 模运算遗漏：每次运算后都要取模，防止溢出
- 初始化错误：注意a[1]应该包含1-9共9个数（不包括0）
- 边界条件混淆：最高位和非最高位的选择数不同
- 零的特殊处理：虽然0个3是偶数，但数字0本身不是有效N位数
我曾在一个项目中需要统计身份证校验码出现的奇偶次数，就采用了类似的动态规划方法。不同的是需要处理更多状态（数字和字母X），但核心的状态转移思想完全相通。
4. 模型扩展：解决更复杂的位数问题
掌握了基础模型后，我们可以将其扩展至更复杂的场景。比如：
多数字统计：同时要求偶数个3和奇数个5的数量。这时状态需要记录两个数字的计数奇偶性，形成四种状态组合：
- (偶3, 偶5)
- (偶3, 奇5)
- (奇3, 偶5)
- (奇3, 奇5)
对应的状态转移矩阵会更大，但原理不变。例如在数字生成时：
- 遇到3：翻转3的奇偶状态
- 遇到5：翻转5的奇偶状态
- 其他数字：保持当前状态
禁止连续数字：要求不能有连续两个相同数字。此时状态需要额外记录前一个数字的值，转移时排除相同选择。这种问题在密码生成策略中很常见。
通用模板代码：
def count_numbers(N, constraints): # constraints定义各种限制条件 dp = {} # 多维状态字典 # 初始化基础状态 # 状态转移循环 # 结果汇总 return result这类问题的解决能力在真实开发中非常实用。比如在设计优惠码生成系统时，我需要确保每批号码满足特定数字分布规律，正是通过扩展这个模型实现了高效统计。记住，动态规划的魅力在于状态定义的创造性——好的状态设计能让复杂问题迎刃而解。
