1. 问题引入从一个看似简单的字符串问题说起最近在整理历年算法竞赛的经典题目时我又翻到了2020年第十一届蓝桥杯国赛C B组的这道“本质上升序列”。说实话第一次看到这个题目名字很多人的第一反应可能和我当初一样这不就是个求上升子序列个数的问题吗动态规划DP的经典例题用dp[i]表示以第i个字符结尾的上升子序列个数然后两层循环累加一下不就完了但如果你真的这么想并且动手去写代码大概率会在某个测试用例上栽跟头。这道题的“本质”二字恰恰是它最大的陷阱和精髓所在。它考察的远不止是基础的动态规划更是对问题定义的深刻理解、对去重逻辑的严密思考以及对算法效率的极致追求。我记得当时赛场上有不少高手都在这里卡了壳不是结果不对就是程序超时。今天我就结合自己多次解题和教学的经验把这道题从里到外、从暴力解法到最优解法的完整思考过程拆解给你看。无论你是正在备赛蓝桥杯的选手还是对算法感兴趣的开发者相信这篇深度解析都能让你对“子序列计数”这一类问题有全新的认识。题目描述通常很简单给定一个全部由小写字母组成的字符串s长度可达200要求计算出其所有“本质不同的上升子序列”的个数并对结果取模通常是10^9 7。这里的“上升子序列”定义为从原字符串中按顺序取出一些字符可以不连续使得这些字符从左到右是严格字典序递增的。而“本质不同”则意味着即使两个子序列由原字符串中不同位置的字符组成只要它们最终形成的字符串完全相同也只能算作同一个子序列。举个例子字符串abac。子序列a取第一个字符和子序列a取第三个字符是同一个字符串a因此它们属于同一个“本质”的子序列只能计一次数。而子序列ab和ac则是两个不同的字符串需要分别计数。我们的目标就是计算所有可能的不同字符串的个数。2. 从陷阱开始为什么不能直接用经典LIS计数DP我们先来看看最直观、也最容易出错的思路——修改经典的最长上升子序列LIS计数DP算法。对于最长上升子序列的计数我们通常会维护两个数组len[i]记录以s[i]结尾的最长上升子序列长度cnt[i]记录以s[i]结尾的、长度为len[i]的上升子序列的个数。然后通过双层循环进行转移。但是请注意LIS计数DP求的是“最长长度”的序列个数并且通常不去重即不同位置构成的相同序列算不同方案。而本题要求的是所有长度的上升子序列不仅仅是最长的。本质不同即最终形成的字符串相同就算同一个。如果我们试图用dp[i]直接表示以s[i]结尾的、所有上升子序列的个数不去重然后最后对所有的dp[i]求和会立刻遇到两个问题问题A如何保证“上升”严格递增这相对好解决在转移时只有当s[j] s[i]j i时才能把以s[j]结尾的序列后面接上s[i]。问题B如何避免重复计数这是核心难点。假设字符串是aba计算dp[2]以最后一个a结尾。当j0时s[0]as[2]a不满足s[j] s[i]所以不能转移。这看起来没问题。但考虑子序列a它既可以是s[0]也可以是s[2]。在我们的定义下dp[0]和dp[2]都包含了只包含一个a的情况即序列本身。如果我们最后简单地将所有dp[i]相加那么子序列a就会被计算两次。你可能会想那我初始化的时候dp[i]只包含长度为1的序列即字符本身然后转移时只从前面更小的字符累加过来不就能避免同一个字符结尾的重复了吗但问题没那么简单。考虑abac我们关注以最后一个c结尾的序列。ac这个序列可以由s[0](a)和s[3](c)组成也可以由s[2](a)和s[3](c)组成。如果我们用dp[3] dp[0] dp[2]那么ac这个字符串就会被计算两次因为dp[0]和dp[2]都包含了a这个前缀。然而dp[0]和dp[2]所代表的a在“本质”上是同一个字符串。因此在向c转移时a这个前缀不应该被重复累加。所以症结在于以不同位置i结尾的dp[i]值可能包含了相同的子序列字符串。直接对dp[i]求和必然导致重复。3. 思维转换按“结尾字符”和“序列字符串”来规划既然按“以位置i结尾”来定义状态会导致重复我们必须换一个角度。题目要求的是不同的“字符串”个数那么我们的状态能不能直接和“字符串”挂钩呢一个关键的洞察是对于一个确定的结尾字符ch比如c所有以ch结尾的本质不同的上升子序列其前一个字符一定是一个比ch小的字符比如a或b并且这些前缀本身也是互不相同的上升子序列。这引导我们定义一个新的状态f[ch]表示以字符ch结尾的、所有本质不同的上升子序列的个数。这里ch是a到z的26个小写字母之一。那么如何计算f[ch]呢假设我们正在遍历原字符串s当前遍历到字符s[i] ch。所有以ch结尾的新序列都可以由“某个以比ch小的字符结尾的旧序列”后面加上ch得到再加上ch本身作为一个单独的序列。因此一个初步的转移方程浮出水面f[ch] sum(f[pre_ch]) 1其中pre_ch遍历所有比ch小的字符sum(f[pre_ch])表示所有可能的、以更小字符结尾的序列后面添加ch所产生的新序列1表示序列ch本身。但是这里依然隐藏着一个巨大的陷阱也是本题最精妙的地方。让我们用字符串abac来手动模拟一下假设我们从左到右遍历读到s[0] a比a小的字符不存在所以f[a] 0 1 1。这表示目前有一个以a结尾的序列a。读到s[1] b比b小的字符有af[a]1。所以f[b] f[a] 1 1 1 2。这两个序列是b和ab。读到s[2] a注意又读到了一个a。按照公式比a小的字符不存在所以f[a] 0 1 1不对如果这样我们就把之前第一个a产生的序列a给覆盖掉了。但实际上新来的这个a它本身作为一个序列a和之前第一个a形成的序列a是“本质相同”的不应该重复创建。然而这个新的a可以作为后续序列的结尾。更重要的是它会影响后续字符的转移吗仔细思考对于后续的字符比如后面的c它可以从前面任意一个a后面接上。但是如果前面有两个a它们提供的、以a结尾的序列集合是完全一样的目前都只有a这一个序列。那么当c计算f[c]时如果简单累加f[a]就会因为f[a]被错误地累加两次实际上两个a对应的是同一个集合而导致重复。所以当我们遇到一个重复的字符时关键点在于不能简单地用1去初始化或更新f[ch]而是要避免对同一“结尾状态”的重复贡献。4. 正解剖析动态规划与容斥原理的结合正确的解法需要结合动态规划和一种类似“容斥”的思想。我们定义dp[i]表示以字符串中第i个位置的字符作为结尾所能形成的所有本质不同的上升子序列的个数。last[ch]一个辅助数组记录字符ch上一次出现的位置索引。初始化为-1。核心思想是当我们遍历到第i个字符s[i] ch时所有以ch结尾的新序列可以由所有在i之前、且字符小于ch的位置j的dp[j]值转移过来。但是如果ch这个字符之前出现过即last[ch] ! -1那么我们需要减去上一次出现时从同样的那些更小字符转移过来的部分因为那部分序列在上一次已经贡献给了以ch结尾的序列集合本次再累加就会导致重复。让我们形式化地描述这个过程并配合abac的例子进行演算初始化dp数组全为0last数组全为-1。总答案ans 0。遍历字符串s的每个位置i(从0开始) a. 当前字符ch s[i]。 b. 我们计算dp[i]的初始值为1代表序列ch本身。 c. 然后我们遍历所有比ch小的字符pre_ch从a到ch-1 * 我们需要知道到目前为止所有以pre_ch结尾的本质不同序列有多少种。注意这不是简单地找最后一个pre_ch的位置因为以pre_ch结尾的序列可能分散在多个位置。实际上所有出现过pre_ch的位置j的dp[j]值之和就是以pre_ch结尾的所有本质不同序列的总数。我们可以维护一个前缀和数组sum[pre_ch]来动态记录这个值。 * 因此dp[i] sum[pre_ch]。这意味着我们可以把每一个以pre_ch结尾的序列后面都添上ch形成一个新的以ch结尾的序列。 d. 现在关键步骤来了如果last[ch] ! -1说明当前字符ch不是第一次出现。在上一次ch出现的位置记为p last[ch]我们在计算dp[p]时也已经加上了当时的所有sum[pre_ch]。那么对于本次计算出的dp[i]其中由sum[pre_ch]转移而来的这部分序列可能在上一次就已经被创建过了如果前缀序列集合没有变化。为了去重我们需要dp[i] - dp[p]等一下这里需要仔细推敲。 更准确地说上一次ch出现时dp[p]已经包含了“从当时的所有更小字符结尾的序列转移过来”的部分。而这一次sum[pre_ch]可能比上一次更大因为中间可能插入了新的以pre_ch结尾的序列。本次新增的、可能产生重复的转移量恰好等于上一次ch出现时它所接收到的转移量也就是dp[p] - 1因为要减去ch本身这个序列。为什么因为本次计算dp[i]时我们加上的sum[pre_ch]是当前的总和。而上一次dp[p]计算时加上的sum[pre_ch]是当时的总和。两者的差值(sum[pre_ch] - sum[pre_ch])是这期间新增的以pre_ch结尾的序列这部分是全新的不会重复。而sum[pre_ch]这部分在上一次已经被用来生成过以ch结尾的序列了所以本次如果再直接用sum[pre_ch]加就会把sum[pre_ch]这部分重复加一次。而sum[pre_ch]就等于dp[p] - 1。 因此正确的去重操作是dp[i] - (dp[p] - 1)不更简洁且正确的写法是dp[i] - dp[p]但需要在更新sum数组之前记录旧的dp[p]值然后本次的dp[i]实际上等于1 sum[pre_ch] - old_dp[p]其中old_dp[p]是dp[p]在本次更新前的值。在实际编码中有一个更清晰的做法 * 先计算一个临时值temp 1。 * 对于每个比ch小的pre_chtemp sum[pre_ch]。 * 如果last[ch] ! -1则temp - dp[last[ch]]。注意这里减去的dp[last[ch]]是上一次出现时计算出的、以那个位置的ch结尾的所有序列数。这个值恰好包含了上一次从所有更小字符转移过来的总量即当时的sum[pre_ch]。 * 然后dp[i] temp。 e. 更新sum[ch] dp[i]。这表示以字符ch结尾的序列总数增加了dp[i]。 f. 更新last[ch] i。 g. 可选将dp[i]累加到总答案ans中。注意dp[i]表示以第i个位置结尾的序列数这些序列彼此本质不同并且与以其他位置结尾的序列也可能本质相同但我们在计算dp[i]时通过减法已经避免了这种重复。最终所有dp[i]的和就是答案。更高效的是在更新sum[ch]后总答案其实就是所有sum[ch]ch从a到z的总和。让我们用abac走一遍这个流程is[i]计算过程 (temp初值1)last[s[i]]旧值减法操作dp[i]最终值更新 sum[s[i]]更新 last[s[i]]累计答案ans (或总sum)0atemp1。比a小的字符无。last[a]-1不减。-1无dp[0]1sum[a]011last[a]0ans11btemp1。比b小的字符有asum[a]1temp112。last[b]-1不减。-1无dp[1]2sum[b]022last[b]1ans1232atemp1。比a小的字符无。last[a]0需要减去 dp[last[a]]即dp[0]1。temp1-10。0temp - dp[0] (1)dp[2]0sum[a]101last[a]2ans3033ctemp1。比c小的字符有a,b。sum[a]1sum[b]2temp1124。last[c]-1不减。-1无dp[3]4sum[c]044last[c]3ans347最终答案 ans 7。让我们验证一下字符串abac的所有本质上升子序列长度为1:a,b,c- 3个长度为2:ab,ac,bc- 3个 (注意aa不上升)长度为3:abc- 1个长度为4: 无 总共 331 7个。符合计算结果。注意a只被计算了一次尽管它出现在两个位置。5. 算法实现与细节打磨理解了原理代码实现就相对清晰了。我们需要维护以下几个数据结构dp[i]以第i个字符结尾的本质不同上升子序列个数。由于我们只需要用到最新的dp[i]来更新sum和last有时可以只用一个临时变量cur。sum[26]sum[ch]表示以字符ch结尾的所有本质不同上升子序列的总数。这是动态更新的前缀和。last[26]last[ch]记录字符ch最近一次出现的位置索引。初始化为 -1。最终答案所有sum[ch]的总和。这里给出一个典型的C实现并附上详细注释#include iostream #include string #include vector using namespace std; const int MOD 1e9 7; // 按题目要求取模 int main() { string s; cin s; int n s.length(); vectorlong long dp(n, 0); // dp[i] vectorlong long sum(26, 0); // sum[ch] vectorint last(26, -1); // last[ch] long long total 0; // 总答案也可以最后累加sum for (int i 0; i n; i) { int ch s[i] - a; long long cur 1; // 序列 s[i] 本身 // 累加所有比当前字符小的字符的 sum for (int pre 0; pre ch; pre) { cur (cur sum[pre]) % MOD; } // 去重如果当前字符之前出现过减去上一次以该字符结尾的序列总数 if (last[ch] ! -1) { // 注意这里减法要加MOD再取模防止出现负数 cur (cur - dp[last[ch]] MOD) % MOD; } dp[i] cur; // 记录当前dp值 sum[ch] (sum[ch] cur) % MOD; // 更新以ch结尾的总数 last[ch] i; // 更新字符ch最后出现的位置 total (total cur) % MOD; // 累加到总答案 } cout total endl; return 0; }几个至关重要的细节和避坑点减法取模cur (cur - dp[last[ch]] MOD) % MOD;这行代码是安全的保证。在模运算中直接做减法可能得到负数加上一个模数MOD再取模可以确保结果在[0, MOD-1]范围内。数据类型使用long long。因为序列个数可能非常多在取模前可能会超过int的范围。初始化与遍历顺序sum数组初始为0last数组初始为-1。遍历字符串的顺序是自然的从左到右这保证了当我们计算cur时sum[pre]已经包含了所有在当前位置i之前出现的、以pre字符结尾的序列信息。为什么是- dp[last[ch]]这是理解去重的核心。dp[last[ch]]包含了上一次出现字符ch时从所有更小字符pre转移过来的序列数即当时的sum[pre]之和。本次计算cur时我们又加上了当前的sum[pre]。当前的sum[pre]等于旧的sum[pre] 期间新增的序列。减去dp[last[ch]]就恰好减去了“旧的sum[pre]”这部分重复累加的量。复杂度分析时间复杂度为 O(26 * n)因为对于每个字符我们需要遍历26个字母中的一部分最多25个来累加sum。对于长度 n200 是绰绰有余的。空间复杂度 O(n26)。6. 举一反三变种问题与思维延伸解决了这道题我们不妨思考几个相关的变种问题这能帮助你巩固这种“状态定义”和“去重”的思想如果不要求“本质不同”只求所有上升子序列的个数不同位置算不同这就简单多了。定义dp[i]为以第i个位置结尾的上升子序列个数允许重复。转移方程为dp[i] 1 sum(dp[j])其中j i且s[j] s[i]。最后答案就是所有dp[i]的和。不需要last数组和去重操作。如果求的是“本质不同的非下降子序列”即允许相等字符个数此时“上升”条件变为s[j] s[i]。去重逻辑需要调整吗需要而且更复杂。因为当s[i] s[j] (j i)时以s[i]结尾的新序列不仅会与之前s[j]结尾的序列重复还可能因为中间插入的相同字符产生新的重复组合。通常的解法是在遍历时对于字符ch我们不仅要从更小的字符转移还要从相同的字符转移但同时要减去最近一次相同字符出现时所累积的、从更小字符转移过来的“增量”部分以避免重复。这需要更精巧地维护状态。如果字符串长度非常大例如10^5字符集也很大比如整个ASCII可打印字符我们内层循环for (int pre 0; pre ch; pre)的复杂度 O(字符集大小) 可能成为瓶颈。此时可以用树状数组Fenwick Tree或线段树来维护sum数组的前缀和。这样求“所有比ch小的字符的sum之和”这个操作可以从 O(K) 优化到 O(log K)其中 K 是字符集大小。通过这道“本质上升序列”我们深刻体会到在动态规划中状态的定义直接决定了问题的复杂度和正确性。当经典思路遇到障碍时不妨退一步重新审视问题的本质约束本题是“本质不同”并尝试将状态与这个约束更直接地关联起来本题从“以位置结尾”转向“以字符结尾”并辅以前缀和与去重。这种思维训练对于解决竞赛中更复杂的计数问题至关重要。