1. 问题引入从一个看似简单的字符串计数问题说起最近在复盘蓝桥杯国赛的真题翻到了C B组的这道“本质上升序列”。题目名字听起来有点唬人什么“本质上升”乍一看像是动态规划或者字符串处理的变种。很多同学第一次看到这个题可能会有点懵不知道从何下手。其实这道题的核心是要求我们从一个给定的字符串中找出所有“本质不同”的“上升子序列”的个数。这里面的两个关键词——“本质不同”和“上升子序列”——就是解题的全部关键。我们先抛开代码用最直白的话来理解一下题意。假设给你一个字符串比如 “lanqiao”。题目问的是从这个字符串里按顺序挑出一些字符可以跳着挑但顺序不能乱使得挑出来的这些字符从左到右是严格递增的‘a’ ‘b’ ‘c’ …。并且即使挑出来的字符在字符串中的位置不同只要最终组成的序列字符串一模一样那就算同一种。这就是“本质不同”的含义。我们的任务就是数一数总共有多少种不同的、严格递增的序列。举个例子会清晰很多。我们用一个更短的字符串 “abc” 来试一下。它的所有“本质上升序列”有哪些呢单个字符 ‘a’, ‘b’, ‘c’。这有3种。两个字符 ‘ab’, ‘ac’, ‘bc’。这有3种。三个字符 ‘abc’。这有1种。 所以总共是 3 3 1 7 种。注意‘ba’ 不是因为 b a不满足递增‘aa’ 也不是因为 a a不满足严格递增。那么如果字符串里有重复字母呢比如 “aab”。它的本质上升序列单个字符 第一个 ‘a’ 第二个 ‘a’ ‘b’。但是两个 ‘a’ 组成的序列都是 “a”在“本质不同”的规则下它们算同一种。所以单个字符只有 ‘a’ 和 ‘b’ 2种。两个字符 序列 “ab” (用第一个a和b)序列 “ab” (用第二个a和b)。看又出现了它们都是 “ab”所以算1种。没有 “aa”因为不严格递增。三个字符 没有因为有两个a无法构成严格递增。 所以总数是 2 1 3 种。看到这里你应该明白了题目的意思。它不是一个简单的求所有子序列的问题而是在此基础上加了两重约束1. 序列必须严格递增2. 要去重。蓝桥杯把它放在国赛B组显然不是让我们用暴力枚举所有子序列2^n复杂度再去重那么简单字符串长度稍微大点就超时了。这背后考察的是动态规划DP的思想和去重的技巧。2. 核心思路拆解动态规划与去重逻辑的融合面对这种计数问题并且有“按顺序”、“递增”的条件动态规划是一个很自然的思路。我们需要设计一个状态以及状态之间如何转移。一个最直接的想法是定义dp[i]表示以字符串中第i个字符结尾的、严格递增的子序列有多少种。那么最终答案就是所有dp[i]的和。状态转移怎么想对于第i个字符s[i]哪些子序列能以它结尾呢所有在它之前出现的、并且字符比它小的位置j(j i 且 s[j] s[i])这些位置j结尾的所有子序列后面接上s[i]就构成了新的、以s[i]结尾的递增子序列。所以dp[i]应该等于所有满足条件的dp[j]之和。但是这里有一个巨大的陷阱也是这道题最精妙的地方重复计数问题。考虑字符串 “abac”。我们来计算以最后一个字符 ‘c’ 结尾的子序列数。位置1: ‘a’, 比 ‘c’ 小dp[1]代表以 ‘a’ 结尾的序列数假设我们算出来是1即序列 “a”。位置2: ‘b’, 比 ‘c’ 小dp[2]代表以 ‘b’ 结尾的序列数它可能包括 “b” 和 “ab”。位置3: ‘a’, 比 ‘c’ 小dp[3]代表以第二个 ‘a’ 结尾的序列数。如果我们简单地把dp[1] dp[2] dp[3]加起来作为dp[4]会出问题。因为以第一个 ‘a’ (位置1) 结尾的序列有 “a”以第二个 ‘a’ (位置3) 结尾的序列也有 “a”。当我们用 “a” “c” 得到 “ac” 时这个 “ac” 会被计算两次一次是通过位置1的 ‘a’一次是通过位置3的 ‘a’。然而根据“本质不同”的定义“ac” 只应该被算作一种。所以直接累加dp[j]会导致对于相同的字符产生重复的转移计数。问题的根源在于对于相同的字符它们能形成的、以该字符结尾的“本质不同”序列集合可能是完全一样的。在上例中以第一个 ‘a’ 和第二个 ‘a’ 结尾的本质不同序列都只有 {“a”}。因此我们需要修正我们的DP策略。一个关键洞察是对于相同的字符我们只关心“最后一次”出现时它所承载的序列种类数。因为更早出现的相同字符它能构成的所有序列在后续的转移中都会被后出现的同一个字符“代表”或“覆盖”。基于这个想法我们调整状态定义和转移方程状态定义dp[i]表示以字符s[i]结尾的、本质不同的严格递增子序列的个数。注意这里强调的是以“这个位置的字符”结尾但计数的已经是去重后的结果。状态转移dp[i] 1 sum(dp[j])其中j满足j i且s[j] s[i]。这个1代表序列只包含s[i]自身的情况。求和sum(dp[j])表示把所有以比s[i]小的字符结尾的序列后面添上s[i]形成新的序列。去重关键操作在计算dp[i]时如果存在k i且s[k] s[i]那么我们需要将之前计算的dp[k]清零或减去。为什么因为以s[k]结尾的所有序列与现在以s[i]结尾的、由更早字符转移而来的序列会产生重复。更准确地说当我们遇到一个新的、与前面相同的字符时我们应该认为以这个字符结尾的序列的“所有权”或“代表性”转移到了这个新的位置。旧位置k的dp值不应该再参与后续任何比s[k]大的字符的转移计算否则就会重复。一种清晰的实现方式是我们维护一个辅助数组last[26]记录每个小写字母最后一次出现时的dp值或者其索引。当我们在位置i遇到字符c时首先正常计算dp[i] 1 sum(dp[j] for j where s[j] s[i])。然后检查last[c]是否存在即字符c之前是否出现过。如果存在假设之前出现的位置是p那么我们就让dp[p] 0。这样在后续计算比c大的字符的dp值时就不会再累加到来自旧位置p的、已经由新位置i“代表”了的序列。另一种等价的、在计算过程中更简洁的思路是在累加sum(dp[j])时对于每一个字符我们只累加它“最后一次出现”时的dp值。我们可以维护一个长度为26的数组sumDp[26]sumDp[ch]表示以字符ch结尾的所有本质不同序列的总数即该字符当前最新的dp值。那么对于当前位置i的字符curdp[i] 1 sum(sumDp[ch])其中ch取所有比cur小的字符。然后更新sumDp[cur] dp[i]。注意这里是直接赋值而不是累加。这就天然实现了“用新的覆盖旧的”完成了去重。第二种思路在编码上更简洁也是解决此题的标准方法。它把去重的逻辑完美地融合到了状态转移的过程中。3. 算法实现详解从理论到C代码理解了上面的核心思路我们就可以着手编写代码了。我们采用第二种思路使用sumDp[26]数组来记录每个字符“当前”的代表性序列总数。假设字符串s的长度为n且只包含小写字母。算法步骤如下初始化一个长度为26的数组sumDp所有元素为0。sumDp[ch]表示以字符ch(‘a’对应0, ‘b’对应1, …) 结尾的本质不同上升序列的个数。遍历字符串s的每一个字符s[i] a. 计算当前字符cur s[i] - ‘a’。 b. 计算dp_i 1。这个1代表序列只包含s[i]自身。 c. 遍历所有比cur小的字符prev(从0到cur-1)将sumDp[prev]累加到dp_i上。这表示所有以更小字符结尾的序列后面接上s[i]构成新的序列。 d. 将sumDp[cur]更新为dp_i。注意这里是赋值不是。这就意味着对于同一个字符我们只保留最后一次计算出的、以它结尾的序列总数。之前的值被覆盖相当于“旧位置”的贡献被移除了。遍历结束后答案就是数组sumDp中所有元素的和。因为sumDp[ch]存储的就是以字符ch结尾的所有本质不同序列数涵盖了所有可能的结尾字符。让我们用字符串 “abac” 来手动模拟一下验证去重是否生效初始化sumDp[26] {0}i0, s[0]’a’, cur0。dp_i 1 sum(sumDp[0…-1]) 1。 (没有比 ‘a’ 小的字符)sumDp[0] 1。 (现在以’a’结尾的序列有1种”a”)i1, s[1]’b’, cur1。dp_i 1 sumDp[0] 1 1 2。 (比’b’小的字符是’a’其sumDp为1)sumDp[1] 2。 (以’b’结尾的序列有2种”b”, “ab”)i2, s[2]’a’, cur0。dp_i 1 sum(sumDp[0…-1]) 1。 (注意此时sumDp[0]还是1但我们累加的是比’a’小的字符没有所以和为0)sumDp[0] 1。 (这里直接覆盖了旧值。虽然值没变但意义是现在以’a’结尾的序列其“代表权”属于位置2的这个’a’。)i3, s[3]’c’, cur2。dp_i 1 sumDp[0] sumDp[1] 1 1 2 4。 (比’c’小的字符有’a’和’b’)sumDp[2] 4。 (以’c’结尾的序列有4种”c”, “ac”, “bc”, “abc”。注意这里的”ac”只被计算了一次因为sumDp[0]是1它代表的是以最后一个’a’结尾的序列数。)最终答案 sumDp[0] sumDp[1] sumDp[2] 1 2 4 7。我们验证一下 “abac” 的所有本质上升序列以 ‘a’ 结尾 “a”以 ‘b’ 结尾 “b”, “ab”以 ‘c’ 结尾 “c”, “ac”, “bc”, “abc” 总共 1 2 4 7 种。正确下面是完整的C实现代码#include iostream #include string #include vector using namespace std; int main() { string s abac; // 这里可以替换成题目给的字符串比如蓝桥杯真题中的长字符串 vectorlong long sumDp(26, 0); // 使用long long防止大数溢出 for (char ch : s) { int cur ch - a; long long dp_i 1; // 序列只包含当前字符自身 // 累加所有比当前字符小的字符的 sumDp 值 for (int prev 0; prev cur; prev) { dp_i sumDp[prev]; } // 关键更新覆盖当前字符的 sumDp 值 sumDp[cur] dp_i; } long long ans 0; for (long long num : sumDp) { ans num; } cout 本质上升序列的个数为: ans endl; return 0; }代码要点与注意事项数据类型由于答案可能非常大远超int范围务必使用long long来存储sumDp和ans。这是竞赛题中非常常见的坑点。去重的核心sumDp[cur] dp_i;这一行是灵魂。它是赋值操作确保了对于每个字符我们只保留其最新最后一次出现的序列总数。时间复杂度O(26 * n)其中n是字符串长度。内层循环最多遍历26次字母表大小对于长度几十万的字符串也完全可行。空间复杂度O(26)只需要一个固定大小的数组非常高效。4. 真题实战与边界情况分析蓝桥杯国赛真题中给出的字符串通常很长比如可能是由某个单词或句子重复构成的。我们的算法可以轻松处理。我们拿一个更复杂的例子来测试一下比如字符串 “abcabc”。按照我们的算法遍历过程会动态更新每个字符的sumDp。最终sumDp[‘a’]将只记录最后一个 ‘a’ 的贡献sumDp[‘b’]和sumDp[‘c’]同理。计算以第二个 ‘c’ 结尾的序列时它所累加的sumDp[‘a’]和sumDp[‘b’]已经是考虑了所有 ‘a’ 和 ‘b’ 的最新、最全的序列集合并且避免了因前面 ‘a’, ‘b’ 重复出现而导致的重复计数。我们可以手动推导或编写小程序验证。对于 “abcabc”其本质上升序列与 “abc” 是一样的吗并不是。因为字符串变长了虽然字符集还是 {a, b, c}但字符出现的顺序和次数增加了能构成的新序列也变多了。例如“a” 可以从第一个或第二个位置取但本质都是 “a”算一种。但序列 “ac” 呢第一个 ‘a’ 和第二个 ‘c’第一个 ‘a’ 和第三个 ‘c’第二个 ‘a’ 和第三个 ‘c’… 实际上根据我们的定义和算法它会正确地计算出所有不重复的递增序列。边界情况考虑空字符串题目通常不会给空串但如果遇到按定义应该是0个序列没有字符可选。我们的算法中for循环不会执行ans初始为0结果正确。单字符字符串如 “a”。算法中dp_i 1然后sumDp[0]1最终ans1。正确只有序列 “a”。所有字符相同如 “aaaa”。严格递增要求序列内字符不同所以只能有单个字符的序列。我们的算法第一个 ‘a’dp1,sumDp[‘a’]1后续的 ‘a’dp始终等于1因为prev循环为空并不断覆盖sumDp[‘a’]为1。最终ans1。正确只有序列 “a”。严格递减字符串如 “cba”。只有单个字符的序列。算法会正确计算每个字符的dp_i都是1因为前面没有更小的字符最终ans3。正确“c”, “b”, “a”。大数处理再次强调用long long。如果字符串很长且字符分布均匀答案是指数级增长的int肯定会溢出。注意在蓝桥杯等竞赛的填空题中答案可能是一个巨大的整数需要直接输出这个数。我们的代码输出ans即可。如果是编程题可能要求对结果取模那就在累加和赋值每一步都进行取模操作。5. 算法对比与思维延伸为什么不是其他方法在思考这道题时可能会想到其他方法我们来分析一下为什么DP是更优解。1. 暴力DFS回溯枚举这是最直观的方法生成字符串的所有子序列检查每个子序列是否严格递增再用一个集合如setstring去重。时间复杂度是 O(2^n * n)其中 n 是字符串长度。生成所有子序列是 O(2^n)检查递增和插入集合是 O(n) 或 O(L log L)L是子序列长度。当 n 超过20时计算量就难以承受了。蓝桥杯国赛的数据规模n 上百是常事此法不可行。2. 基于位置的传统子序列DP定义dp[i]为考虑前 i 个字符能形成的本质不同上升子序列个数。这个状态很难转移因为新增一个字符s[i]时它不仅可以接在以前面字符结尾的序列后面还可以自己作为起点更麻烦的是它还会和前面相同的字符产生重复序列。状态定义没有聚焦于“以谁结尾”导致去重异常复杂。相比之下我们采用的“以字符结尾”的状态定义配合sumDp数组巧妙地将去重转化为“覆盖更新”简化了问题。3. 基于字符集的DP我们的方法其实就是一种基于字符集的DP。状态是“以某个字符结尾”而不是“以某个位置结尾”。因为题目只关心序列的字符内容严格递增和是否重复不关心这些字符具体来自原字符串的哪些位置只要顺序正确。这种视角转换是降低问题复杂度的关键。它利用了字母表只有26个的小范围特性将复杂度从 O(n^2) 降到了 O(26*n)。思维延伸如果字符集很大呢如果字符串不是小写字母而是任意ASCII字符甚至Unicode我们的sumDp数组大小就不再是26了。此时一种方法是使用有序映射如C的mapchar, long long来动态维护比当前字符小的所有字符的dp值之和。在遍历每个字符时我们需要快速求出所有键小于当前字符的值的和并更新当前字符的键值。这可以通过树状数组Fenwick Tree或线段树来实现将字符离散化后在值域上维护前缀和。这样时间复杂度可以做到 O(n log C)其中C是字符集大小。这体现了该DP模型良好的可扩展性。6. 常见错误与调试技巧在实现和调试这道题时初学者容易遇到以下几个坑1. 忘记使用 long long这是最致命的错误。因为本质上升序列的数量可能增长得非常快。例如一个完全递增的字符串 “abcdefghijklmnopqrstuvwxyz”其本质上升序列的数量等于所有非空子集的数量即 2^26 - 1大约是6.7亿还在int范围内。但如果字符串更长或者字符排列方式特殊数量很容易超过 2^31。在竞赛中一旦溢出结果就完全错误了。养成习惯在不确定范围时对于计数类DP优先使用long long。2. 去重逻辑写错写成了累加错误的代码sumDp[cur] dp_i;这会导致重复计数。例如 “aa”正确答案是1只有”a”但累加会得到2第一个’a’算1第二个’a’又加了1。务必记住是赋值sumDp[cur] dp_i;3. 内层循环的边界弄错计算dp_i时累加的是prev从 0 到cur-1即所有严格小于当前字符的字符。如果写成prev cur或者prev cur但起始值不对都会导致错误。可以画一个字母表来帮助理解。4. 初始化问题sumDp数组应初始化为0。dp_i每次要初始化为1代表自身。这些细节在纸上演算时是清晰的但写代码时可能遗漏。调试技巧小数据测试用短字符串如 “a”, “ab”, “aa”, “abc”, “aab” 手动计算预期结果与程序输出对比。打印中间变量在循环中打印出每一步的cur、dp_i和sumDp数组观察其变化是否符合预期。例如对于 “abac”一步步跟踪看是否和我们之前的手动模拟一致。对比暴力法仅用于小数据验证写一个简单的DFS暴力枚举程序对于 n 10 的小字符串验证DP算法的结果是否正确。这是验证算法正确性的黄金标准。7. 举一反三同类问题与变种思考掌握了“本质上升序列”的解法我们可以看看一些类似的问题巩固这种DP思想。变种1计算不同的上升子序列个数LeetCode 类似题LeetCode上有类似题目比如计算一个整数数组的不同递增子序列的个数。整数范围可能很大。这时我们的“字符”变成了整数字符集可能很大。解决思路依然是定义dp[i]为以nums[i]结尾的不同递增子序列个数。转移dp[i] 1 sum(dp[j])其中j i且nums[j] nums[i]。去重对于相同的数值nums[i]我们需要避免重复。一种方法是对于每个值我们只累加它最后一次出现时的dp值。可以在遍历时用一个哈希表记录每个数值最新的dp值之和或者更精确地说是到当前位置为止以该值结尾的序列总数。当遇到重复值时用新的dp值覆盖旧值在哈希表中的记录。计算当前dp[i]时需要累加所有比nums[i]小的值的“最新dp值”。这通常需要对nums离散化后用树状数组维护前缀和以实现 O(n log n) 的复杂度。变种2最长递增子序列LIS的计数问题经典的最长递增子序列LIS问题是求长度。它的一个变种是求最长递增子序列的个数。这比本题更难一些因为不仅要计数还要保证序列是最长的。通常需要两个DP数组一个记录长度一个记录方案数并在转移时根据长度关系来决定如何累加方案数。去重逻辑也更为复杂。变种3带有禁止位的上升序列如果题目增加条件比如某些字符不能同时出现在序列中或者序列必须包含某个特定字符等。这通常需要在状态定义中增加维度例如用位掩码来表示哪些字符已经被使用过将问题转化为状态压缩DP。通过解决“本质上升序列”这道题我们深入练习了以结尾元素定义状态的DP方法以及利用覆盖更新来处理去重的经典技巧。这种“只关心最后一次出现”的思想在需要处理重复元素贡献的计数DP问题中非常常见是一个值得牢记的套路。下次遇到类似需要计数字符串或数组中满足某种条件的、去重后的子序列个数时不妨先想想能不能用这种“结尾元素DP覆盖去重”的模型来解决。