2022年5月20号前后各平台算法比赛扎堆我在一套叫“520钻石争霸赛”的题单里看到7-8题名字是“521序列”。当时第一反应是出题人又在玩数字梗5月20号表白5月21号就是“我爱你”的延续。点开题面才发现这个梗背后藏着的是一道非常标准的数位DP统计题——给你一个区间[L,R]要统计区间里有多少个整数它的十进制数位中按顺序包含5、2、1这三个数字L和R的数据范围给到了10^18这个量级。这篇文章就围绕这道题展开从题意理解、DP状态设计、完整可提交代码到我自己重写时踩过的几个坑一次性讲透。无论你是在准备蓝桥杯、天梯赛还是单纯想补一补数位DP这块短板这篇都值得收藏。先说结论这道题的核心不是“521”这个梗而是你知不知道怎么在10^18的区间里快速数数。暴力枚举每一位的复杂度是O(N * 位数)数据一大就完全没法看。数位DP是解决这类问题的标准姿势而“521序列”恰好是一个非常适合入门的模板题因为它的状态转移够简单但又不像纯计数题那么枯燥。1. 先看懂“521序列”到底在数什么1.1 题目定义与一个容易踩的“子串/子序列”误区不同平台上这道题的表述会有一点点差异但最主流的定义是如果一个数的十进制表示中存在位置ijk使得第i位是5、第j位是2、第k位是1那就称这个数为“521序列”。换句话说5、2、1这三个数字要按顺序出现但中间可以夹其他数字。这里就藏着一个很关键的区分子序列匹配和子串匹配。举几个例子你就明白了15213数位依次是1,5,2,1,3。其中第2位是5、第3位是2、第4位是1所以包含521子序列也包含连续子串“521”算合法。51213数位依次是5,1,2,1,3。第1位是5、第3位是2、第4位是1满足子序列条件但十进制里并没有连续出现“521”所以如果题目定义的是“连续子串”这个数就不算。31415926这个数里有5、2、1吗有。第5位是5、第7位是2、第8位是1满足子序列条件但它完全不包含连续“521”。我一开始看到“序列”两个字默认是按子序列做的结果对拍时发现怎么都对不上。后来仔细回看题面才知道很多平台的版本其实要求的是“子序列521”但还有一部分改编版要求的是“连续子串521”。这两种定义对应的状态转移完全不同后面第5章我会专门把两者都讲清楚。所以在做题之前第一件事永远是拿样例验证定义而不是急着写代码。这个习惯比任何模板都重要。1.2 暴力跑一遍看看它为什么必须换思路为了彻底理解题目我一开始还是老老实实写了个暴力程序bool check(long long x) { string s to_string(x); bool has5 false, has52 false; for (char c : s) { if (c 5) has5 true; else if (c 2 has5) has52 true; else if (c 1 has52) return true; } return false; }这个写法是按子序列匹配的状态其实已经和DP一致了has5表示是否见过5has52表示是否见过完整的“5→2”最后来了1就返回true。逻辑没问题但你看一下复杂度如果L1、R10^18要跑10^18个数每个数最长19位就算每位数只要几个时钟周期这个量级在普通机器上也得跑到天荒地老。暴力代码存在的意义不是用来AC而是用来做两件事第一验证你对题意的理解第二写一个对拍器拿小数据去验证DP算法的正确性。我当时暴力跑了一下1到10000的结果只有15个数合法。这个数据可以直接当成验算基准。等你把DP写完跑同样的区间如果答案不是15说明你的状态转移一定有问题。2. 数位DP把“区间统计”拆成“逐位填空”2.1 前缀和思想solve(R) - solve(L-1) 是怎么来的数位DP最核心的一个思路就是不要直接统计[L,R]区间而是拆成两个前缀区间solve(R)减去solve(L-1)。其中solve(x)表示[0,x]范围内满足条件的数有多少个。为什么可以这样拆因为“从0到x有多少个满足条件的数”这个问题比“从L到R有多少”更简单——它只需要你处理一个上界x而不是同时处理两个边界。这是典型的容斥思想和前缀和数组sum[R] - sum[L-1]是一个道理。solve(x)本身是怎么工作的把x的每一位拆出来存进一个数组里。比如x1234拆成digits [4,3,2,1]低位在前。然后从最高位开始一位一位地尝试填数字。每填一位的时候你需要知道当前这位能不能填到9还是只能填到x在这一位的值。这就是经典的limit状态。如果你现在对“limit”这个概念还比较模糊可以这样想你在填一个N位数的密码最高位不能超过x的最高位。如果最高位填得比x的最高位小那后面几位随便填0到9都没问题如果最高位填得和x一样大那第二位的选择范围就要受x的第二位限制。limittrue就是在说“我前面每一笔都贴着x填所以当前这位也得小心不能越界”。2.2 state 从 0 到 3匹配长到哪一步了判断一个数是不是“521序列”不需要记录“前两位具体是什么”只需要记录一个匹配进度目前为止我已经匹配到了模式“5→2→1”的哪一步。这个进度用一个整数state来表示state0还没看到5state1已经看到了5正在等一个2state2已经看到了5和2正在等一个1state3模式完整出现这个数已经确定为合法后面无论填什么都不改变了。有人可能会问为什么不需要记录前一位、前两位因为子序列匹配的特点就是“只要按顺序出现过就行”前面出现过的东西不会因为后面又来一个数字而消失。这是它比连续子串匹配简单的地方。连续子串匹配才需要关注最近几位。从state和当前位d可以得到新状态的转移表当前stated5d2d1其他数字01000112112223233333这个表值得你多看几眼因为它是整道题的灵魂。有几个容易想不明白的转移我展开说当state1、当前位d5时状态还是1不是回到0。因为“5 5 2 1”里第一个5已经可以当作起点第二个5也不影响这个起点我们只需要一个5状态保持1即可。当state2、当前位d5时状态继续保持2不用降级。因为我们已经完成了“5→2”这个成就不会因为又出现一个5而清零。后面只要再来1立刻就是合法数。当state1、当前位d1时状态还是1。因为当前需要一个21不能推进匹配但已经出现的5仍然有效后面随时可能来2。2.3 limit 和记忆化同一个状态为什么能复用dfs函数的参数通常是五个pos还剩多少位、state匹配进度、limit是否贴住上界、lead是否为前导零。在每一层递归里枚举当前位填0到upup由limit决定int up limit ? digits[pos] : 9;核心优化在于记忆化。如果当前状态是limit 且 lead意味着后面可以随便填0到9不受任何限制。那么这个状态的答案和“我们在处理哪一个数”就没有关系了。比如pos3、state1意思是“还剩3位要填已经有一个5在手里”不管x是12345还是99999这个状态下后面3位随便填的结果数是一样的。所以我们用dp[pos][state]把它记下来。但如果limittrue说明当前这位被上界卡住了每次输入不同后续选择范围也不同这个状态的结果不能被复用。所以所有数位DP模板都有一个铁律只有limit时才能存取dp表。lead这个参数略微特殊。它表示“到目前为止填的数是否仍然是前导零”。比如数字521如果统一按5位填会被拆成0,0,5,2,1。如果不管lead直接拿0去更新匹配状态理论上也不会出错因为前导零并不会“伪造”出一个5、2、1来。但加上lead会让代码更通用万一以后题目改成“统计含连续子串的个数”对前导零的处理就更稳妥。所以我个人建议模板里保留lead。3. 代码实现一个dfs函数解决全部匹配逻辑3.1 完整的可用于提交的C代码下面这份代码是我按“子序列521”的定义写的可以直接提交到大多数OJ。注释写得比较细建议跟着注释走一遍。#include bits/stdc.h using namespace std; typedef long long ll; int digits[25], len; ll dp[25][4]; int goMatch(int st, int d) { if (st 3) return 3; // 已经匹配完成后面不用管 if (st 0 d 5) return 1; // 第一次看到5 if (st 1 d 2) return 2; // 看到5之后看到2 if (st 2 d 1) return 3; // 看到52之后看到1 return st; // 其余情况匹配进度不变 } ll dfs(int pos, int st, bool limit, bool lead) { if (pos 0) return st 3 ? 1 : 0; if (!limit !lead dp[pos][st] ! -1) { return dp[pos][st]; } ll ans 0; int up limit ? digits[pos] : 9; for (int d 0; d up; d) { int nst st; if (!(lead d 0)) { // 前导零不进匹配逻辑 nst goMatch(st, d); } ans dfs(pos - 1, nst, limit (d up), lead (d 0)); } if (!limit !lead) dp[pos][st] ans; return ans; } ll solve(ll x) { if (x 0) return 0; len 0; while (x 0) { digits[len] x % 10; x / 10; } memset(dp, -1, sizeof(dp)); return dfs(len - 1, 0, true, true); } int main() { ll L, R; while (cin L R) { cout solve(R) - solve(L - 1) \n; } return 0; }这段代码的核心只有两个函数goMatch负责状态转移dfs负责枚举和记忆化。整体思路就是前两章讲的没有任何奇技淫巧。3.2 逐段拆解模式转移goMatch为什么只写三行goMatch的写法本质就是把2.2那张状态表翻译成if语句。你可能会有疑问为什么state1、当前位d5时走的是“return st”而不是单独一个if因为这个情况对应“状态不变”直接用最后的return st处理就行不需要额外写。同理state2、当前位d5也是归到return st。但这里有个隐藏细节goMatch里如果st3我会直接返回3不进入后面任何判断。这个提前返回非常关键。假如没有这一行代码虽然也能跑对但会出现一个逻辑漏洞st3时后面来了数字5会先触发“st0 d5”吗不会因为st不是0。会不会触发“st1 d2”也不会。所以其实后面几个if都进不去最终走到return st返回3。逻辑上也不会错。但我还是建议显式写上因为这能让读代码的人一眼看出“匹配完成之后状态锁定”也防止以后扩展逻辑时不小心破坏掉。dfs里的枚举部分有一个细节很多人第一次会写错limit (d up)这个参数。当d刚好等于当前位的上界时下一位继续受限只要d小于up后面就彻底自由了。注意这里不是limit d digits[pos]虽然因为up limit ? digits[pos] : 9在某些分支里dup和ddigits[pos]是等价的但在!limit时up是9dup表示d9这样会错误地把“自由状态”继续当成受限状态。所以正确写法一定是limit (d up)。3.3 记忆化状态与数组尺寸的陷阱dp数组为什么开dp[25][4]第一个维度是pos最多20位就够10^18是19位我习惯多开点第二个维度是state只有0,1,2,3四种状态。这个数组非常小完全不用担心内存。但正因为数组小新手很容易掉进一个陷阱不把dp初始化为-1而是默认0。这是数位DP最经典的一个坑。因为很多合法状态的结果本身就是0比如pos3、state0、后面三位随便填但已经确定凑不出5→2→1的情况dfs结果就是0。如果你用0当“未计算”的标记那么每次递归到这里都会认为已经算过了直接返回0。幸运的是这个场景下返回0恰好是对的于是BUG不会立刻显现而一旦出现一个非0情况被错误缓存答案就崩了。所以记住dp初始化为-1这是约定俗成的规矩不要省那一次memset。4. 重写过程中我踩过的几个真实坑4.1 memset(-1)的位置放错答案一直偏小我第一次写这份代码的时候把memset放在了main函数外面想着省一点重复初始化的开销。结果第一组样例过了第二组样例开始答案就偏小。查了很久才发现solve(L-1)和solve(R)虽然x不同但dp表如果保留上一次的缓存值按理说也不该出问题因为状态本身不依赖x的具体值。问题出在哪出在solve函数里我用了全局变量len而x0的时候直接return 0、没有重置len导致后续dp的pos维度索引错乱。正确的做法就是像上面代码那样把memset(dp, -1, sizeof(dp))放在solve函数内部、dfs调用之前。这样不论输入多少组数据每次都是干净的状态。虽然多了一点O(25*4)的开销但这点开销完全可以忽略换来的是心理上的绝对安稳。4.2 limit状态误存进dp表导致TLE另一个我见过很多的错误是有人把limit也作为记忆化条件写进dp表比如dp[pos][st][limit]。从正确性上说这不一定错但是记忆化效果会大打折扣。因为limittrue的状态在每次solve里只有一条路径会遇到它的结果几乎不会被复用但你为它分配了存储和写入开销还可能因为memset不及时导致错误缓存。更严重的是如果有人在!limit的时候读取了limittrue时写入的值答案就完全错了。正确写法就是模板中的只有!limit !lead才存取dp。这个剪枝条件不是锦上添花而是数位DP正确性和效率的保证。4.3 暴力对拍一夜下来唯一靠谱的调试方式我写算法题有一个习惯新学的DP模板一定要配一个暴力程序做对拍而且是小数据对拍。以这题为例我写了一个暴力版本check函数然后生成随机数据反复验证DP结果。对拍的具体跑法很简单。写一个批处理脚本循环执行生成随机的L、R范围控制在1到100000跑暴力程序得到答案ans1跑DP程序得到答案ans2如果ans1 ! ans2打印当前L、R并退出。对拍脚本可以长这样while true; do echo $(( RANDOM % 100000 1 )) $(( RANDOM % 100000 1 )) in.txt ./brute in.txt out1.txt ./digital_dp in.txt out2.txt if ! diff -q out1.txt out2.txt /dev/null; then echo WA found cat in.txt break fi done注意生成L、R时要保证L R可以在脚本里做一次大小交换。这种自动化对拍方式能帮你在一分钟之内跑完上百万组小数据远比肉眼盯代码找BUG靠谱。我那天晚上就是靠这个脚本抓出了自己在lead处理上的一个逻辑漏洞改完直接AC。5. 两种变体与扩展不只是“521”这一道题5.1 如果原题要求的是连续子串“521”怎么办如果题目定义不是“子序列”而是要求十进制表示中必须连续出现“521”比如51213不算、15213才算那改法也非常简单只需要替换goMatch函数。连续子串匹配的状态仍然是0到3但转移逻辑要变因为“前面已经匹配到的前缀”在遇到不匹配的字符时可能会失效。对于“521”这个短模式转移可以直接硬编码int goMatchSubstring(int st, int d) { if (st 3) return 3; // 按KMP的思想看当前字符能延续多长的模式前缀 if (d 5) return 1; // 任何状态下碰到5都重新开启一个候选前缀 if (d 2) return (st 1) ? 2 : 0; // 只有已经匹配到5时2才有意义 if (d 1) return (st 2) ? 3 : 0; // 只有已经匹配到52时1才完整收官 return 0; // 其他字符所有前缀全部作废 }我们来验证几个关键场景st1、d5表示当前已经匹配到“5”又来了一个5。连续串“55”里最长有效的模式前缀还是“5”所以返回1。上面代码d5直接返回1正确。st2、d5表示当前已匹配“52”又来一个5。字符串“525”的后缀里只有最后一个“5”能作为新的匹配起点所以返回1。同样正确。st2、d2表示“522”。后缀“22”不是前缀“5”也不是“52”所以状态清零返回0。上面代码d2时st不是1返回0正确。这个硬编码版本只适用于“521”这种长度3的模式。如果模式再长一点比如“1314”手写判断就很容易漏情况这时候需要上KMP自动机。5.2 把模式串换成任意串KMP状态机写法通用的做法是先把模式串的next数组求出来然后建一个自动机从任意状态i读入字符c转移到新的状态j表示“当前已匹配长度为i加入字符c之后最长能匹配到模式前缀的长度”。构建核心代码非常短vectorint buildNext(const string pat) { int m pat.size(); vectorint nxt(m 1, 0); for (int i 1, j 0; i m; i) { while (j 0 pat[i] ! pat[j]) j nxt[j]; if (pat[i] pat[j]) j; nxt[i 1] j; } return nxt; } int trans[20][10]; void buildAutomaton(const string pat) { int m pat.size(); vectorint nxt buildNext(pat); for (int st 0; st m; st) { for (int d 0; d 9; d) { int cur st; while (cur 0 (cur m || pat[cur] - 0 ! d)) cur nxt[cur]; if (cur m pat[cur] - 0 d) cur; trans[st][d] cur; } } }这样无论模式是“521”“1314”还是“5201314”数位DP的dfs部分一行都不用改只需要把goMatch替换成读trans表。这种做法的好处是通用可以作为一个标准的“禁止/必须包含某个模式串的数位DP模板”攒着。5.3 进阶统计每个数字里“521”出现次数而不是个数有些加强版本的题目不满足于问“有多少个数字包含521”而是问“区间内所有数字里521出现了多少次”要求把重叠的也算上。这种题的DP状态不能只存一个bool因为最终要累加的贡献变成了“出现次数”而不是“是否为合法数”。改法有两种第一种是dp返回值变成出现总次数。在dfs转移时如果当前这一步让状态从2变成了3就给这一整支加上1的贡献然后继续递归。核心代码是ll dfs(int pos, int st, bool limit, bool lead) { if (pos 0) return 0; ... for (int d 0; d up; d) { int nst goMatch(st, d); ll add (nst 3 ? 1 : 0); // 本次新出现了一次完整的521 ans dfs(pos - 1, nst, limit d up, lead d 0) add; } ... }第二种是维护两个返回值。实际比赛里第一种更常见因为代码改动最小。但要注意如果模式是可重叠的比如“111”一个数字“1111”应该算两次还是算三次这个需要跟题面对齐。“521”这个模式本身没有重叠风险所以第一种写法完全够用。数位DP这个技巧一旦你吃透了很多“看着很难”的计数题都会变得套路化。核心永远是状态设计、limit、记忆化三者缺一不可。遇到“区间内统计含某模式数字”的题先判断模式是子串型还是子序列型再决定转移函数怎么写剩下的dfs框架基本是通用的。那次比赛之后我把这个dfs模板存了下来后来做其他字符串模式计数题时直接套省了非常多时间。建议你也这样试试先手写一遍再改成自己习惯的模板比死记硬背别人的代码效果好得多。