1. 什么是数位DP数位DPDigit DP是一种用于解决「在某个数值区间内统计满足特定条件的数字个数」问题的动态规划算法。它的核心思想是把数字按位拆开从最高位到最低位逐位进行状态转移从而避免暴力枚举每一个数字。数位DP非常适合处理诸如「1到N之间有多少个数字不包含数字4」「某个区间内有多少个数字满足各位数字之和等于K」这类问题。这类问题如果直接暴力遍历当N达到10的18次方甚至更大时计算量会爆炸式增长而数位DP可以在O(位数 × 状态数)的时间复杂度内高效求解。2. 核心思想与状态设计数位DP的核心思想可以概括为「按位枚举 状态压缩」。我们从数字的最高位开始一位一位地决定当前位可以填什么数字同时用状态记录已经确定的前缀信息避免重复计算。在数位DP中最经典的状态设计包含以下几个维度位置pos当前处理到数字的第几位从高位到低位。是否紧贴上界limit表示当前位之前的所有位是否已经和N的前缀完全一致。如果一致当前位能取的最大值受N当前位的限制否则可以取0到9任意值。前导零标记lead表示当前是否仍然处于数字的前导零阶段用于处理「0」和「00」这类特殊情况。题目特定状态例如已经出现的数字集合、各位数字之和、是否已经出现过某个数字等根据具体题目灵活设计。通过记忆化搜索Memoization我们可以把「在某个位置、某个状态下后续还有多少种合法填法」的结果缓存起来从而避免大量重复子问题的计算。3. 经典模板与代码实现下面给出数位DP最经典的模板使用记忆化搜索实现。该模板以「统计1到N之间不含数字4的数字个数」为例进行说明。#include bits/stdc.h using namespace std; int digit[20]; // 存储N的每一位 long long dp[20][2]; // dp[pos][limit]记忆化数组 // pos当前位limit是否紧贴上界 long long dfs(int pos, bool limit) { if (pos -1) return 1; // 所有位都填完返回1种合法方案 if (!limit dp[pos][limit] ! -1) return dp[pos][limit]; int up limit ? digit[pos] : 9; // 当前位能取的最大值 long long ans 0; for (int i 0; i up; i) { if (i 4) continue; // 跳过数字4 ans dfs(pos - 1, limit i up); } if (!limit) dp[pos][limit] ans; return ans; } long long solve(long long n) { int len 0; while (n) { digit[len] n % 10; n / 10; } memset(dp, -1, sizeof(dp)); return dfs(len - 1, true); } int main() { long long n; cin n; cout solve(n) endl; // 输出1到n之间不含数字4的个数 return 0; }这段代码的核心在于dfs(pos, limit)函数它返回「从第pos位开始在limit状态下后续能填出的合法数字个数」。当limit为false时说明前缀已经小于N后续所有位都可以自由填0到9此时结果与N无关可以安全地存入记忆化数组。4. 实战案例统计不含某数字的个数我们以「统计1到N之间不含数字4的数字个数」为例详细拆解数位DP的执行过程。假设N 345第一步把345拆成位数组digit[0]5digit[1]4digit[2]3。第二步从最高位百位开始搜索。百位可以填0、1、2、3。当填0或1或2时limit变为false后续十位和个位可以自由填0到9但跳过4当填3时limit保持true十位受digit[1]4限制。第三步递归到十位。如果limit为false十位可以填0到9跳过4个位同理如果limit为true十位只能填0到4跳过4且填4时个位受digit[0]5限制。第四步递归到个位填完最后一位后返回1逐层累加得到最终答案。通过这个例子可以看出数位DP的本质是把「枚举所有数字」转化为「枚举每一位的取值」配合记忆化把大量重复的「后缀状态」合并计算从而大幅降低时间复杂度。5. 进阶技巧前导零与特殊状态在实际题目中前导零的处理是一个常见难点。例如统计「1到N之间各位数字之和为K的数字个数」时前导零会影响数字的位数判断因此需要引入lead状态来区分「当前是否还在前导零阶段」。下面给出一个带前导零处理的模板用于统计「1到N之间各位数字之和为K的数字个数」#include bits/stdc.h using namespace std; int digit[20], K; long long dp[20][200][2][2]; // pos, sum, limit, lead long long dfs(int pos, int sum, bool limit, bool lead) { if (pos -1) return (sum K) ? 1 : 0; if (!limit !lead dp[pos][sum][limit][lead] ! -1) return dp[pos][sum][limit][lead]; int up limit ? digit[pos] : 9; long long ans 0; for (int i 0; i up; i) { if (lead i 0) { // 仍然处于前导零阶段sum不变 ans dfs(pos - 1, sum, limit i up, true); } else { ans dfs(pos - 1, sum i, limit i up, false); } } if (!limit !lead) dp[pos][sum][limit][lead] ans; return ans; } long long solve(long long n) { int len 0; while (n) { digit[len] n % 10; n / 10; } memset(dp, -1, sizeof(dp)); return dfs(len - 1, 0, true, true); }在这个模板中lead为true时表示当前所有已填的位都是0此时填0不会增加数字和一旦填了非零数字lead变为false后续所有位都正常累加数字和。这样就能正确处理「0」「5」「123」等不同位数的数字。6. 常见题型与解题思路数位DP的题型非常丰富但万变不离其宗。以下是几类常见题型及其解题思路不含特定数字在枚举每一位时直接跳过禁止的数字如上面的「不含4」例子。各位数字之和在状态中增加sum维度记录当前数字和最后判断是否等于目标值。区间统计利用前缀和思想solve(R) - solve(L-1)即可得到区间[L, R]内的答案。回文数需要记录前半部分的数字在枚举后半部分时进行对称匹配状态设计相对复杂。整除类问题在状态中记录当前数字对某个数取模的结果例如统计能被3整除的数字个数。无论题型如何变化核心都是「找准状态维度 设计好转移方程 用记忆化剪枝」。建议初学者从「不含特定数字」和「数字和」这两类基础题入手熟练掌握后再挑战回文数、整除等进阶题型。7. 总结数位DP是算法竞赛中非常实用的一类动态规划它通过按位枚举和状态压缩把看似需要暴力遍历的计数问题转化为高效的递推求解。掌握数位DP的关键在于理解limit和lead两个核心状态的作用能够根据题目要求灵活设计额外的状态维度并熟练运用记忆化搜索避免重复计算。建议读者在理解模板的基础上多动手练习几道经典题目逐步体会「状态设计」的精髓。只要吃透本文的模板和思路遇到新的数位DP题目时就能举一反三快速找到突破口。