2022年5月20日晚上我在拼题A上把520钻石争霸赛前面几道题都刷完之后点开了最后一道压轴的7-8 521序列。说实话被题目标题逗笑了——前面刚做完一堆“520”表白题最后一道还来个“521”。但笑归笑这道题其实是整个比赛里最能体现动态规划基本功的一道题目看起来很甜蜜考的东西却很实在——统计一个字符串里有多少个“521”子序列。这道题我印象比较深因为它属于典型的“一眼看上去能暴力但数据一放大就完蛋”的题目。如果你刚接触算法竞赛或者对动态规划还停留在“听过但不太会用”的阶段那这篇题解应该能帮你把“子序列计数”这一类问题的套路彻底吃透。我会从题目理解、状态设计、代码实现到扩展变形全部拆开讲尽量让小白也能跟上节奏。1. 题目到底让咱们干什么先别急着写代码1.1 题面里的“521序列”指什么520钻石争霸赛的题目风格偏趣味化但算法内核不会放水。这道7-8 521序列的常见题面大概是这样的给定一个只包含数字字符的字符串S请你统计S中有多少个子序列恰好等于字符串521也就是能按原顺序挑出若干个字符依次组成5、2、1这三个数字。这里有个概念必须先掰扯清楚子序列不是子串。子串要求字符在原串里必须连续比如1521里的521是连续的一段但子序列只要求相对顺序不变字符之间可以有间隔甚至可以把整个字符串里不相邻的5、2、1都挑出来拼成一个521。举个很直观的例子字符串512里有没有521子序列答案是0因为2出现在1前面顺序反了。但552211里就有很多个521子序列因为我们可以从两个5里任选一个、两个2里任选一个、两个1里任选一个一共8种选法。题目要求的往往就是统计这样的数量并且结果要对一个大质数取模常见的是1e97。这种“取模 计数”的组合在竞赛里太常见了基本是动态规划题的标配。1.2 数据范围会说话为什么暴力枚举必死第一次见到这题的人第一反应大概率是我能不能用三层for循环枚举每一个5、再枚举它后面的每一个2、再枚举2后面的每一个1每次遇到就计数加一在小数据下确实可以比如字符串长度只有几十的时候三层循环跑得飞快。但问题恰恰出在数据范围上。这类题目字符串长度轻轻松松给到10的5次方甚至10的6次方如果一共有多个5和多个2、多个1组合数会爆炸式增长。你想想极端情况下比如字符串是555...222...111每类字符各10万多个三层循环的复杂度是O(n^3)操作次数直接奔着10的15次方去了就算服务器再强也扛不住。更麻烦的是子序列的个数本身可能非常大。一个长度为n的全5再配上一堆2和1合法子序列数量可能是三个数的乘积轻松超过10的18次方根本不适合用int或者long long直接存。所以题目要求取模既是为了防止溢出也是暗示你题目本质是在数数而不是在枚举。1.3 这道题考察的核心能力“521序列”这个题的核心考点就是如何用动态规划在线性时间内完成子序列计数。更准确地说它考察的是你能否把一个“匹配到哪一步”的过程抽象成状态并用状态数组来维护“以某种前缀结尾的方案数”。我见过不少同学一听到“动态规划”就害怕觉得必须列一大堆公式。其实这道题真正写下来状态就三个数字连数组都不用开。它的本质和“统计一个字符串里有多少个指定子序列”是同一类问题掌握了这道题后面遇到“520”“1314”甚至任意模式串的计数都能直接套同一个模板。2. 动态规划思路把“匹配进度”变成状态2.1 从空序列开始四个状态怎么设计很多人卡就卡在状态不会设计。这道题一个很自然的想法是我们一路扫描字符串每看到一个字符就想想它能不能成为521这串里的某一个位置。于是可以把“当前已经匹配到的进度”作为状态dp0匹配到空前缀的数量也就是“什么都没有匹配”的方案数dp1匹配到5的数量也就是已经选好了一个字符作为5dp2匹配到52的数量也就是已经选好了5和它后面的某个2dp3匹配到521的数量也就是完整匹配成功的数量。这个思路特别像我们在玩一个个位数的状态机每读一个字符看它是否能让某个状态向前推进。而dp0的初始值要设为1因为一开始我们手里拿着一个空的子序列这也是一种方案后面每一个5都可以基于这个空子序列来延伸。这里有一点要特别注意dp1记录的不是“当前字符5的个数”而是“以5结尾的合法前缀数量”。比如字符串里出现了3个5那么dp1最终会是3意思是单独挑出任意一个5作为前缀都有1种方案一共3种。dp2则代表“已经形成52这个前缀”的数量它是由所有可能的5和后面位置的2配对产生的。2.2 转移方程是怎么一步步推出来的现在假设我们扫描到了一个新的字符c它只可能是三种情况等于5、等于2、等于1或者都不是。都不是的时候就什么都不用做直接跳过因为一个无关字符不可能成为521中的任何一位。如果c等于5它只可能作为整个序列的第一个字符。它能接在谁后面当然是空串后面。所以转移就是dp1 dp1 dp0这里的含义是要么不选当前这个5沿用之前已经匹配到5的方案数要么选当前这个5作为新产生的“5”前缀数量就是之前空串的数量。如果c等于2它只能作为52里的第二个字符。它能接在哪个状态后面是已经匹配到5的前缀后面。所以转移是dp2 dp2 dp1同理如果c等于1它只能接在52后面形成完整的521dp3 dp3 dp2全程扫描一遍字符串最终答案就是dp3。你可能会问为什么遇到2的时候不去更新dp1或dp3因为同一个字符在子序列里只能用一次而且它必须严格对应521里的某一位。如果某个字符是2它既不能当5也不能当1它只能充当第二个位置。这个“一个字符只能推进一个状态”的约束正是这个DP不重不漏的关键。2.3 为什么可以用变量搞定“已经匹配到某一位”的计数这道题的空间复杂度可以做到O(1)连数组都不用开。原因很简单我们只关心模式串521的匹配进度而进度只有0、1、2、3四种所以四个long long变量就足够。但如果你以前写过最长上升子序列之类的题可能会担心一个问题同一个字符会不会被重复使用比如字符串5521第一个5更新了dp1第二个5又更新了dp1当遇到2的时候dp2一次性把两个5都算进去了这会不会导致同一个5被2重复配对不会。dp1里存的本来就是“当前已经遇到过的所有可能的5前缀”dp2在遇到2的时候继承的是这个总数每一种前缀和当前这个2组合都是新的合法子序列互相独立并不会重复计数。这也正是动态规划比暴力枚举聪明的地方暴力是“一个一个配”动态规划是“把同类的方案数合并在转移时统一继承”。理解了这个思想后面所有子序列计数问题你都会觉得简单很多。3. 代码实现与关键细节3.1 最简四变量版本C和Python写法先上一个最直接的实现四变量滚动更新复杂度O(n)空间O(1)。#include bits/stdc.h using namespace std; const long long MOD 1000000007LL; int main() { string s; cin s; long long dp0 1; // 空前缀 long long dp1 0; // 匹配到 5 long long dp2 0; // 匹配到 52 long long dp3 0; // 匹配到 521 for (char c : s) { if (c 5) { dp1 (dp1 dp0) % MOD; } else if (c 2) { dp2 (dp2 dp1) % MOD; } else if (c 1) { dp3 (dp3 dp2) % MOD; } } cout dp3 % MOD endl; return 0; }Python版本更短思路完全一致import sys MOD 1000000007 s sys.stdin.readline().strip() dp0, dp1, dp2, dp3 1, 0, 0, 0 for c in s: if c 5: dp1 (dp1 dp0) % MOD elif c 2: dp2 (dp2 dp1) % MOD elif c 1: dp3 (dp3 dp2) % MOD print(dp3 % MOD)有的同学可能会疑惑dp0为什么一直不更新因为“空前缀”只有一种那就是什么都不选所以dp0始终保持为1。这个1是起点是后面所有转移的火种千万不要在循环里把它顺手改掉。3.2 通用版本把模式串变成参数如果你只满足于写出521的解法那有点可惜。因为这类题有一个更通用的模板给定一个模式串P求出它在原串S中作为子序列出现的次数。520争霸赛系列题里经常出现类似的变体今天出521明天可能就出520或者1314。通用做法是用一个数组dp[j]表示“匹配到模式串P的前j个字符”的方案数其中dp[0]1表示空串。扫描原串时看到字符c就从后往前更新所有能匹配的位置。long long countSubsequence(const string s, const string p) { int m p.size(); vectorlong long dp(m 1, 0); dp[0] 1; for (char c : s) { for (int j m - 1; j 0; j--) { if (c p[j]) { dp[j 1] (dp[j 1] dp[j]) % MOD; } } } return dp[m]; }注意内层循环为什么要从后往前这非常关键。如果从前往后更新假设模式串是55原串只有一个字符5正序更新时dp[1]先变成1然后j1时又用新的dp[1]去更新dp[2]导致单个字符被当成两个字符用了两次凭空多出一个不存在的55子序列。从后往前更新就不会有这个问题因为更新后面的状态时前面的状态还是这一轮扫描之前的值天然保证了“同一个字符最多参与一次匹配”。四变量版本其实也是这个通用模板的特例因为521三个字符互不相同正序倒序都不会出错。但写成通用版之后无论模式串长什么样都不会翻车。3.3 那些坑更新顺序、取模、数据类型的坑第一坑是忘记取模。dp1、dp2、dp3在极端情况下会变得非常大。比如字符串是10万个5后面跟着10万个2再跟着10万个1dp3最终可能是10万的三次方这个量级远超int范围。用long long能撑到大约10的18次方但三个10万相乘是10的15次方还在long long范围内可如果数据范围再大一点比如每类字符出现100万个那就直接爆了。所以每一步加法都要取模不要等到最后才取。第二坑是初始化。dp0必须初始化为1而不是0。如果你把dp0设成0遇到第一个5时dp1还是0后面dp2、dp3全是0答案永远是0。这个错误我见人踩过很多次尤其在现场赛紧张的时候特别容易犯。第三坑是字符串里可能有空格或者其他非数字字符。题目一般说只含数字但保险起见代码里遇到无关字符直接跳过就行不会影响结果。第四坑是输出格式。答案要换行取模之后可能等于0那也是合法答案不要觉得“0就是没算出来”。比如字符串里根本没有1答案必然是0。4. 变式与扩展一道题变成一类题4.1 统计任意模式串的子序列出现次数通用模板的价值在于它把问题抽象成了“模式匹配 计数”和具体是521还是520完全无关。你只需要把模式串改掉比如改成520那遇到字符0时就更新dp3其他逻辑一模一样。这种题在女性向的节日题里出现频率极高因为出题人总喜欢把题目包装成“520”“521”“1314”之类的浪漫字符串。如果你在比赛里看到“统计字符串中‘XYX’子序列数量”这类题也一样可以用这个模板。唯一需要注意的是模式串里如果有重复字符比如121那通用版里的倒序更新就绝对不能省略因为正序更新会让同一个字符在同一轮里被重复使用。4.2 统计“521521...”这种重复模式有时候题面会加一个花样统计子序列等于521521甚至连续重复很多次521的子序列数量。这种题看着唬人其实还是同一个模板模式串直接写成521521521就行。不过模式串长度变长了时间复杂度会从O(n)变成O(n × m)m是模式串长度。如果m不大完全没问题如果m很大比如几千甚至几万那就要考虑用自动机或者矩阵快速幂来优化了不过那已经是进阶内容竞赛里很少考到那种程度。还有一种变体是不要求子序列完整等于521而是问“能凑出多少个由5、2、1组成的序列并且长度至少为3”。这种就要维护更多状态了本质上是一个二维DP不过思路还是沿着“当前以什么数字结尾”展开先把基础模板吃透再看那些变体就会觉得有迹可循。4.3 如果同样数字很多怎么验证答案我刷题时有个习惯代码写完先不急着提交先找几组数据手算验证一下。对于521这个题最典型的验证数据就是输入521答案应该是1这是最简单的正例输入512答案是0因为2和1顺序反了输入552211答案是8因为两个5任选一个、两个2任选一个、两个1任选一个2×2×28输入521521答案是4。这个稍微复杂一点我第一次手算也算错过后来按DP推了一遍才确认。通过这种手算验证你能很快发现自己写的状态转移有没有问题。如果程序跑出来的结果和手算不一致那就说明转移方程或者更新顺序有bug趁早回头改。4.4 特殊数据的处理细节除了常规数据还要考虑边界情况字符串为空直接输出0程序不能崩字符串只有一个字符5输出0字符串是555555缺少2和1输出0字符串超级长比如10的6次方保证程序能在几毫秒内跑完用cin记得关同步流或者直接用scanf。边界数据是竞赛里最常见的扣分点。很多人的核心逻辑是对的但边界数据没处理白丢二十分。写题的时候养成习惯先把空串、单字符、全同字符这类极端情况想清楚代码的健壮性会好很多。5. 测试样例与常见问题排查5.1 几组可以直接自测的数据我自己在调试时通常会准备一组自测用例把它们整理成表格方便对照输入字符串期望输出说明5211最基本的正例5120顺序反了没有任何合法子序列55221182个5 × 2个2 × 2个15215214两组数字互相穿插需要认真推5550缺少2和1210缺少5空串0边界情况5215551多个5在最后但不能重复使用如果你把这些数据全部跑通代码基本就稳了。尤其是521521这组如果你能推明白为什么答案是4说明你已经真正理解了整个DP过程。5.2 常见错误速查表我在实际刷题和帮别人debug的过程中总结了一些高频错误整理成下面这个速查表建议保存一下错误表现原因解决办法答案一直为0dp0初始化成了0或者循环中把dp0改掉了dp0固定初始化为1不要动它答案比预期大更新顺序搞错同一字符被重复使用四变量版本检查逻辑通用版本一律倒序更新答案溢出变负数忘记取模或数据类型用了int使用long long每步加法后取模结果不稳定字符串读取时混入了空格或换行用getline或strip清理输入输入超时cin没有关同步流加ios::sync_with_stdio(false)这五个问题基本覆盖了我见过的大部分提交失败原因。你可以把这张表当成checklist每次提交前快速过一遍能省下不少罚时。5.3 复杂度的最终确认最后再对一下复杂度单次扫描字符串每个字符做常数次操作所以时间O(n)。如果n10的6次方这个算法也可以在1秒内跑完非常轻松。空间上只用了4个long long变量是O(1)。如果使用通用版本复杂度为O(n × m)m为模式串长度。对于像521这样长度为3的模式依然是线性的。因此无论题目怎么包装只要模式串长度是常数这道题都稳过。6. 一点实测体会从比赛到日常刷题这道题我在实际比赛里用了不到一分钟就写完了因为看到“统计子序列”这个关键词脑子里瞬间就浮现出“dp[j]表示匹配到第j位”的模板。后来我在日常刷题时发现这种套路能解的不止浪漫数字题很多字符串、排列、组合计数题本质上都是同一个思路把一个组合计数的过程拆成状态用前一个状态的结果推后一个状态。我个人的体会是这种题最怕的不是不会DP而是把简单问题想复杂了。有人一上来就想要不要用后缀数组、要不要用自动机、要不要搞容斥原理结果反而把自己绕晕。竞赛里很多题就是这样看起来花里胡哨核心其实就是一个很朴素的DP。先把手上的小样例手工模拟一遍把转移方程列清楚再写代码这才是最快的路径。最后再分享一个小技巧如果比赛时间紧张不想推转移方程可以直接套通用模板把模式串当作参数传进去一样能AC。但平时练习我不建议这么做因为手动推一遍“521”的转移过程对你理解状态设计帮助特别大。以后遇到再复杂的计数题回头想想这道题是怎么从“空串”一路推到“521”的思路就不会乱。