从零基础到独立刷完经典数位 DP 题沉淀出一套固定骨架的通用写法换题只需要改状态维度和约束判断核心逻辑永远不变。一、核心总思想永远不变前缀和转化求区间[L, R]的答案 dp(R) - dp(L-1)dp(n)计算[0, n]中所有满足条件的数的对应结果所有数位 DP 题都先拆成「算上界 - 算下界减一」通用套路永不变二、通用代码骨架标准写法1. 全局变量区固定结构typedef long long LL; const int N 20; // 位数上限1e18开20足够二进制开60 vectorint nums; // 存拆出来的每一位数字 LL f[N][...][...]; // 记忆化数组维度 pos 所有状态参数 // 若需要返回多个值用 struct 或 pair维度规则第一维永远是pos后面跟所有状态参数0/1 状态占一维枚举类状态如 last、cnt对应开大小2. dfs 函数核心永远五步走返回值 dfs(int pos, 状态1, 状态2, ..., int t, int l) { // 第1步边界判断所有位填完 if(pos -1) return 满足条件的边界值; // 第2步记忆化查询算过直接返回避免重复计算 if(f[pos][状态1][状态2]...[t][l] ! -1) return f[pos][状态1][状态2]...[t][l]; // 第3步确定当前位数字上界 int up t ? nums[pos] : 9; // 二进制改1B进制改B-1 返回值 res 初值; // 计数类初值为0乘积类初值为1 // 第4步枚举当前位数字执行状态转移 for(int j 0; j up; j) { // 4.1 计算下一层的固定状态 int nt t (j up); // 下一层是否仍受上界限制 int nl l (j 0); // 下一层是否仍处于前导零 // 4.2 计算下一层的题目自定义状态 新状态1 根据j和旧状态推导; 新状态2 根据j和旧状态推导; // 4.3 题目约束校验不满足直接跳过 if(不满足题目条件) continue; // 4.4 递归下一层合并结果 res dfs(pos-1, 新状态1, 新状态2, ..., nt, nl); // 取模题目在此处加 % mod } // 第5步存入记忆化数组返回当前状态结果 f[pos][状态1][状态2]...[t][l] res; return res; }3. dp 函数固定流程LL dp(LL n) { if(n 0) return 0; // 边界保护必加 nums.clear(); // 清空上一次的数位必加 // 拆数十进制模10二进制模2B进制模B while(n) { nums.push_back(n % 10); n / 10; } memset(f, -1, sizeof f); // 重置记忆化数组必须写在dp函数内 // 调用dfs传入初始状态 return dfs(nums.size()-1, 初始状态1, 初始状态2, ..., 1, 1); }4. 主函数固定写法int main() { LL L, R; cin L R; LL ans dp(R) - dp(L-1); // 取模题目写LL ans (dp(R) - dp(L-1) mod) % mod; cout ans endl; return 0; }三、状态设计通用套路固定三参数几乎每题必有题目自定义状态按题目需求新增核心原则所有影响「后续合法性」「后续结果计算」的信息全部塞进状态维度。四、常见题型的返回值与合并方式五、必踩坑点 Checklistmemset 位置必须写在dp函数内部不能只写在 main换数字、换目标 d 都要重置缓存数组越界初始占位值如 last11不能超过数组维度大小开数组要留余量前导零判断校验约束用当前层的l不是下一层的nl前导零状态下约束不生效状态传参递归必须传新计算出的状态不能误传旧状态前缀和负数取模题目结果必须(dp(R) - dp(L-1) mod) % mod防止负数位数限制题如手机号必须 11 位不足位数直接返回 0避免前缀和多减输入逆序部分题目 L 可能大于 R先执行 swap 再计算n0 保护dp 函数开头必加if(n0) return 0避免 L1 时 L-1-1 触发异常六、可直接套用的空白模板纯计数版绝大多数纯计数类数位 DP 题往里填约束和状态即可#includebits/stdc.h using namespace std; typedef long long LL; const int N 20; vectorint nums; LL f[N][2][2]; // pos 自定义状态 tight lead LL dfs(int pos, 自定义状态, int t, int l) { if(pos -1) return 合法条件 ? 1 : 0; if(f[pos][自定义状态][t][l] ! -1) return f[pos][自定义状态][t][l]; int up t ? nums[pos] : 9; LL res 0; for(int j 0; j up; j) { int nt t (j up); int nl l (j 0); 新状态 状态转移逻辑; if(题目约束不满足) continue; res dfs(pos - 1, 新状态, nt, nl); } return f[pos][自定义状态][t][l] res; } LL dp(LL n) { if(n 0) return 0; nums.clear(); while(n) { nums.push_back(n % 10); n / 10; } memset(f, -1, sizeof f); return dfs(nums.size()-1, 初始状态, 1, 1); } int main() { LL L, R; cin L R; cout dp(R) - dp(L - 1) endl; return 0; }