1. 项目概述一道经典的动态规划“计数”难题如果你刷过蓝桥杯国赛的真题尤其是C/C B组那么“本质上升序列”这道题绝对是一个绕不开的坎。它不像某些题目那样一眼就能看出是DFS或者贪心这道题的核心在于“计数”而且计的是“本质不同”的序列数量。乍一看题目描述可能并不复杂给定一个字符串要求计算出其所有“本质不同”的上升子序列的数量。但就是这个“本质不同”让无数选手在赛场上挠头也让这道题成为了区分算法功底深浅的试金石。我当年第一次碰到这道题时也陷入了思维定式试图用回溯去重结果复杂度直接爆炸。后来静下心来结合动态规划和集合论的思想才真正理解了其精妙之处。这道题完美地融合了字符串处理、动态规划状态定义以及去重逻辑是提升对DP理解深度的绝佳材料。它不仅考察你会不会写状态转移方程更考察你能否精准地定义“状态”来规避重复计数。无论是备战蓝桥杯还是希望夯实动态规划基础吃透这道题都能让你受益匪浅。2. 核心概念解析什么是“本质上升序列”要解决这个问题我们必须先掰开揉碎彻底理解题目的每一个约束条件。这不仅仅是读懂题更是为后续设计算法打下坚实的基础。2.1 问题重述与定义题目通常这样描述给定一个全部由小写字母构成的字符串s例如lanqiao我们需要找出其所有的“本质不同的上升子序列”。这里的术语需要逐一明确子序列由原字符串在不改变字符相对顺序的情况下删除某些字符也可以不删除后形成的新序列。例如对于abca,ab,ac,bc,abc都是它的子序列。空序列通常也被认为是子序列但在此类计数问题中需要根据题目要求确认是否计入。上升在此题语境下“上升”指的是子序列中每个字符的ASCII码值单调递增。也就是说对于子序列s[i1], s[i2], ..., s[ik]必须满足i1 i2 ... ik且s[i1] s[i2] ... s[ik]。注意是严格递增不是非递减。本质不同这是本题最大的难点。两个子序列如果其构成的字符串完全相同则它们被视为同一个即“本质相同”。例如字符串aba中选取第一个和第三个字符‘a‘, ‘a‘形成的子序列aa与选取第二个和第三个字符‘b‘, ‘a‘不这不符合上升规则。我们换一个例子abab。考虑上升子序列ab。它可以通过选取索引 (0,1) 的字符得到也可以通过选取索引 (0,3) 的字符得到因为‘a‘‘b‘且索引03。虽然来自原字符串的不同位置但形成的序列都是ab因此它们只被计数一次。所以题目的最终目标就是统计给定字符串s中所有字符严格递增的、且字符串表示互不相同的子序列的个数。2.2 一个简单的例子让我们用s abc这个最简单的例子来直观感受一下。 所有可能的、字符严格递增的子序列有长度为1a,b,c(3个)长度为2ab,ac,bc(3个)长度为3abc(1个) 总数为 331 7。由于abc中每个字符都唯一所以这里所有序列自然就是“本质不同”的。答案就是7。再看一个稍复杂的例子s aba。 我们需要找出所有严格递增的子序列长度为1a,b,a。注意这里有两个a但它们来自字符串的不同位置索引0和索引2。根据“本质不同”的定义它们形成的字符串都是a所以只能算1个。因此长度为1的本质不同子序列是{a “b“}共2个。长度为2 可能的有“ab“(索引0,1) 和“ab“(索引0,2)? 等等索引(0,2)是‘a‘, ‘a‘不满足严格递增。那么“ba“(索引1,2) 呢‘b‘ ‘a‘也不满足。所以唯一满足递增的只有“ab“(索引0,1)。长度为2的本质不同子序列只有{ab“}共1个。长度为3“aba“不满足严格递增。 因此对于“aba“答案是 2 1 3。通过这两个例子我们应该能清晰感受到“本质不同”的要求意味着我们不能简单地枚举所有索引组合然后判断是否上升因为那样会重复计数相同的字符串。我们必须以一种能够自动合并相同结果的方式进行计数。3. 暴力思路与瓶颈为什么不能直接枚举拿到问题最朴素的想法就是生成字符串的所有子序列检查每个子序列是否严格上升最后用一个集合如setstring来存储满足条件的子序列的字符串形式集合的大小就是答案。这个思路的代码如下C示意#include iostream #include set #include string using namespace std; void dfs(const string s, int index, string current, setstring result) { if (index s.length()) { if (current.length() 0) { // 非空子序列 // 检查current是否严格上升 bool isIncreasing true; for (int i 1; i current.length(); i) { if (current[i] current[i-1]) { isIncreasing false; break; } } if (isIncreasing) { result.insert(current); // 利用set去重 } } return; } // 不选当前字符 dfs(s, index 1, current, result); // 选当前字符 current.push_back(s[index]); dfs(s, index 1, current, result); current.pop_back(); } int main() { string s “lanqiao“; // 示例字符串 setstring res; string cur; dfs(s, 0, cur, res); cout res.size() endl; return 0; }这个方法的致命缺陷是什么时间复杂度。一个长度为n的字符串其子序列总数高达2^n个每个字符选或不选。当n较大时比如蓝桥杯真题中长度可能达到200甚至更多2^200是一个天文数字完全无法在限定时间内通常1秒完成计算。因此暴力枚举集合去重的路径是行不通的。我们必须寻找一种更高效、无需显式生成所有子序列就能完成“计数”和“去重”的方法。注意这里有一个关键点即使我们优化检查过程比如在DFS过程中维护当前序列的最后一个字符保证加入新字符时是递增的我们仍然需要遍历指数级的搜索空间并承受set插入和比较字符串的巨大开销。对于算法竞赛这绝对是下策。4. 动态规划DP的核心思路拆解既然不能枚举所有子序列我们就必须用动态规划来“数”出这个结果。DP的精髓在于利用已解决的子问题来构建当前问题的解避免重复计算。对于此题我们需要设计一个状态它既能表征“以某个位置结尾”的信息又能巧妙地处理“本质不同”的去重。4.1 状态定义的探索与确定最直接的想法之一是定义dp[i]表示以字符串中第i个字符s[i]作为最后一个字符的、严格上升的本质不同子序列的个数。这个定义初看有点道理但我们试着用它来思考转移。对于dp[i]我们如何从j i的状态dp[j]转移过来条件是s[j] s[i]。那么dp[i]似乎应该等于所有满足s[j] s[i]的dp[j]之和再加上字符s[i]自身作为一个长度为1的子序列的情况即1。但这里有一个巨大的问题重复计数。 考虑字符串s “abab“。我们计算dp[3](以最后一个‘b‘结尾)。j0:s[0]‘a‘ ‘b‘,dp[0]代表以第一个‘a‘结尾的子序列数假设我们正确计算了dp[0]1(只有“a“)。那么dp[0]的这些子序列后面加上‘b‘会得到“ab“。j2:s[2]‘a‘ ‘b‘,dp[2]代表以第三个字符‘a‘结尾的子序列数。关键来了在s[0…2]“aba“这个子串中以第二个‘a‘结尾的本质不同上升子序列有哪些它自己“a“是一个。但是这个“a“和以第一个‘a‘结尾的“a“是“本质相同”的如果我们简单地把dp[2]也加进来那么由dp[2]1贡献的“a“ ‘b‘得到的“ab“就和由dp[0]贡献的“ab“重复了。所以简单的dp[i] 1 sum(dp[j]) for j i and s[j] s[i]会导致对于相同字符结尾的子序列其贡献被重复累加进而使得以其为前缀构建的更长子序列也被重复计数。正确的状态定义需要能区分以字符‘x‘结尾且这个‘x‘是字符串中“最后一次出现”的‘x‘吗不我们需要更根本的解决。4.2 基于字符集的状态定义与去重原理为了从根本上避免重复我们必须改变视角。既然“本质不同”关心的是最终的字符串是什么那么我们就应该以“子序列的最后一个字符是什么”作为状态划分的依据而不是“以原字符串中第几个字符结尾”。定义dp[c]表示当前所有以字符c结尾的、本质不同的严格上升子序列的个数。这里c的范围是小写字母‘a‘到‘z‘。现在我们按顺序遍历原字符串s的每一个字符s[i]。对于当前遍历到的字符ch s[i]我们思考如何更新整个dp数组。更新逻辑如下对于字符ch本身它可以作为一个全新的、长度为1的子序列。所以dp[ch]至少应该增加1。更重要的是对于所有 ASCII 码小于ch的字符c‘所有以c‘结尾的现有子序列在其末尾追加当前字符ch后都能形成一个新的、以ch结尾的、且严格上升的子序列。并且由于我们是从所有以c‘结尾的子序列扩展而来而dp[c‘]已经保证了这些子序列彼此“本质不同”那么扩展后得到的以ch结尾的新子序列也一定是“本质不同”的。如何更新我们不能简单地dp[ch] dp[c‘]因为dp[ch]本身可能已经包含了一些子序列来自之前对ch的处理。我们需要的是以当前这个s[i]作为子序列最后一个字符的新序列数量。这个数量等于1 sum(dp[c‘]) for all c‘ ch。这里的1代表ch自身单独成序列。关键的去重操作但是请注意s[i]这个字符可能在字符串前面已经出现过。例如在“aba“中当i2遇到第二个‘a‘时如果我们只是计算new_sequences_for_this_a 1 sum(dp[c‘] for c‘ ‘a‘)由于没有字符小于‘a‘所以new_sequences_for_this_a 1。如果我们把这个1直接加到dp[‘a‘]上那么dp[‘a‘]就会变成2这代表了{“a“ (from index0), “a“ (from index2)}但它们是本质相同的这就重复了。所以正确的做法是对于当前字符ch我们计算出一个“新增量”add 1 sum(dp[c‘]) for c‘ ch。然后我们将dp[ch]直接更新为这个add而不是累加。为什么 因为dp[ch]记录的是“以字符ch结尾的本质不同子序列”。当我们在字符串中再次遇到字符ch时之前以ch结尾的子序列由更早出现的ch生成已经记录在dp[ch]里了。现在这个新出现的ch它可以和所有小于它的字符结尾的子序列结合形成新的一批以ch结尾的子序列。同时它自己单独也是一个。这两部分合起来就是“到当前位置为止所有以字符ch结尾的本质不同子序列”。而之前旧的dp[ch]值由更早的ch生成的那些序列实际上可以被当前这个新的、更全面的集合所覆盖。因为对于后续大于ch的字符来说它们可以接在任何一个以ch结尾的序列后面无论这个序列是由第一个ch还是第二个ch参与构成的只要序列字符串相同就是同一个。所以我们必须用最新的、最全的集合来代表dp[ch]。简单来说dp[ch] 1 sum(dp[c‘]) for c‘ ch每次遇到字符ch都执行这个赋值操作而不是。4.3 算法流程与示例演算让我们用s “aba“来完整走一遍这个DP过程。dp[26]数组初始全为0。处理s[0] ‘a‘计算add 1 sum(dp[c‘] for c‘ ‘a‘)。小于‘a‘的字符没有所以sum 0。add 1。更新dp[‘a‘] add 1。 此时dp[‘a‘]1表示以‘a‘结尾的序列有{“a“}。dp状态dp[‘a‘]1 其他为0。处理s[1] ‘b‘计算add 1 sum(dp[c‘] for c‘ ‘b‘)。小于‘b‘的字符有‘a‘。sum dp[‘a‘] 1。add 1 1 2。更新dp[‘b‘] add 2。 这2个序列是{“b“ “ab“}。其中“ab“是由dp[‘a‘]中的“a“后面加‘b‘得到的。dp状态dp[‘a‘]1dp[‘b‘]2。处理s[2] ‘a‘计算add 1 sum(dp[c‘] for c‘ ‘a‘)。sum 0。add 1。更新dp[‘a‘] add 1。 注意这里是赋值不是累加。所以dp[‘a‘]从1变成了1。这个新的1代表的是以当前这个‘a‘字符串末尾的‘a‘结尾的本质不同子序列。它包含了“a“自己。那之前以第一个‘a‘结尾的“a“呢它们本质相同所以被覆盖/替换了。此时dp[‘a‘]1仍然只表示{“a“}这一个序列成功去重dp状态dp[‘a‘]1dp[‘b‘]2。最终答案遍历所有字符c将dp[c]累加起来。ans dp[‘a‘] dp[‘b‘] 1 2 3。这与我们之前手动计算的结果一致。再验证一个例子s “abab“。i0,‘a‘:dp[‘a‘]1。 ({“a“})i1,‘b‘:add 1 dp[‘a‘]2。dp[‘b‘]2。 ({“b“ “ab“})i2,‘a‘:add 1。dp[‘a‘]1。 (覆盖仍然是{“a“})i3,‘b‘:add 1 dp[‘a‘]2。dp[‘b‘]2。 (注意这里把dp[‘b‘]更新为2而不是224。这2代表的是以当前这个‘b‘结尾的新序列集合{“b“ “ab“}。它和之前dp[‘b‘]表示的集合完全一样因为“a“后面接‘b‘得到的还是“ab“。)最终ans dp[‘a‘] dp[‘b‘] 1 2 3。 我们手动列举一下长度为1:“a““b“长度为2:“ab“。总共3个。正确。5. 代码实现与逐行解析理解了上述原理代码实现就非常清晰了。以下是完整的C实现#include iostream #include string #include vector using namespace std; int countDistinctIncreasingSubsequences(const string s) { // dp数组对应26个小写字母。dp[0]代表‘a‘ dp[25]代表‘z‘。 vectorlong long dp(26, 0); // 遍历字符串中的每一个字符 for (char ch : s) { // 计算所有小于当前字符的dp值之和 long long sum_less 0; for (int c 0; c (ch - ‘a‘); c) { sum_less dp[c]; } // 当前字符能形成的、以它结尾的新子序列数量 1自己 sum_less long long new_count 1 sum_less; // 关键直接赋值而不是累加以实现去重 dp[ch - ‘a‘] new_count; } // 统计所有以任意字符结尾的本质不同上升子序列总数 long long total 0; for (long long num : dp) { total num; } return total; } int main() { string s; // 假设输入字符串例如蓝桥杯真题可能是 “tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl“ // 这里用简单例子测试 s “lanqiao“; int result countDistinctIncreasingSubsequences(s); cout result endl; return 0; }代码关键点解析数据类型使用long long。因为结果可能非常大远超int范围。蓝桥杯国赛的数据规模往往要求使用64位整数。dp数组初始化大小为26初始值为0。dp[i]表示以字符(char)(‘a‘i)结尾的本质不同上升子序列的个数。核心循环for (char ch : s)顺序遍历字符串。顺序至关重要它保证了我们构造子序列时字符的相对顺序与原串一致。内层循环for (int c 0; c (ch - ‘a‘); c)计算所有ASCII码小于当前字符ch的dp值之和即sum_less。这代表了所有可以接上当前字符ch形成更长上升子序列的“基础序列”数量。new_count 1 sum_less1是当前字符自成序列sum_less是所有小于它的字符结尾的序列后面追加它。这两部分合起来就是以当前这个位置的ch作为序列结尾能形成的所有新序列。dp[ch - ‘a‘] new_count这是去重的灵魂。直接赋值意味着我们只关心“到最后一次出现字符ch的位置为止”以ch结尾的序列有哪些。之前的记录被覆盖因为对于后续字符来说它们只需要知道以ch结尾的序列集合是什么而不关心这个集合是由哪个ch产生的。最终求和遍历dp数组将所有值相加即为所有可能的、非空的、本质不同的严格上升子序列总数。复杂度分析时间复杂度O(26 * n)其中 n 是字符串长度。因为对于每个字符我们最多需要累加26个dp值。这是一个非常高效的线性算法。空间复杂度O(26)即常数空间。6. 边界情况、陷阱与实战技巧即使理解了算法在竞赛中实现时也可能踩坑。下面是一些必须注意的细节和提升代码鲁棒性的技巧。6.1 空序列是否计入这是一个必须明确的边界条件。题目描述有时会明确说明“非空子序列”。在我们的算法中dp值计算时包含了每个字符自身1所以最终求和total是包含了所有非空子序列的。如果题目要求包含空序列只需要在最终结果上加1即可。但根据蓝桥杯历年真题的惯例和“上升”的定义空序列通常不被认为具有“上升”属性默认不包含空序列。在比赛时务必仔细阅读题目的输出描述。6.2 大整数溢出问题这是本题最大的陷阱之一。字符串长度可能达到200本质不同的上升子序列数量可以非常庞大。例如对于一个完全递增的字符串“abcdefghijklmnopqrstuvwxyz“其本质不同上升子序列数等于所有非空子集数即2^26 - 1约等于6.7亿还在int范围内。但如果字符串更长或者字符集更集中导致组合更多结果很容易超出int甚至long的范围。在C/C中long在Windows平台通常是4字节和int一样。因此必须使用long long64位整数来存储dp值和最终结果。这是国赛题目的常见考点。6.3 初始化与更新顺序dp数组初始化为0是没问题的。更新顺序就是字符串的遍历顺序这符合子序列的定义。内层循环求sum_less时必须严格遍历所有小于当前字符的索引。这里不能优化成维护一个前缀和数组吗理论上可以但考虑到字母只有26个直接遍历的代价极小且逻辑清晰不易错竞赛中完全足够。6.4 测试用例设计自己编写代码后一定要用多种用例测试简单用例“a“- 1“ab“- 3“aa“- 1“aba“- 3。全递增长串“abcde“-2^5 - 1 31。可以用组合数学验证长度为k的严格递增子序列有C(5, k)个总和为C(5,1)C(5,2)…C(5,5)31。全相同串“aaaa“- 1。因为只有“a“这一种子序列。复杂串“abab“- 3“acbac“可以手动计算验证。最大规模随机测试生成长度200的随机字符串用你的DP代码和一个暴力DFSSet的代码仅用于小规模验证如n15进行对拍确保结果一致。实操心得在竞赛中对于这种计数DP我习惯在写完代码后立刻用最小的例子如“a“和全相同例子如“aaa“测试这两个例子往往能快速暴露初始化或更新逻辑的错误。7. 算法扩展与思维提升解决这个问题后我们不妨思考一些相关的变种或更深层次的问题这能极大锻炼我们的算法思维。7.1 如果求“非递减”子序列呢将条件从“严格递增” () 改为“非递减” ()即允许相等字符出现在子序列中。此时状态定义和转移需要如何调整核心矛盾在于去重。对于“aa“非递减子序列有“a“,“a“,“aa“。其中两个“a“本质相同。如果沿用之前的dp[ch] new_count赋值法当处理第二个‘a‘时new_count 1 sum(dp[c‘] for c‘ ‘a‘)注意这里条件变成了c‘ ‘a‘那么sum就包含了dp[‘a‘]自身来自第一个‘a‘。new_count 1 dp[‘a‘] 112。这表示以当前这个‘a‘结尾的新序列有“a“(自己) 和“aa“(由之前的“a“接上当前‘a‘)。而dp[‘a‘]被更新为2。最终所有dp值求和时dp[‘a‘]2代表了{“a“ “aa“}。咦我们发现两个“a“被成功地合并为了一个。这是因为在计算当前‘a‘的new_count时我们加上了之前dp[‘a‘]这相当于把“以前一个‘a‘结尾的序列”后面再追加一个‘a‘从而形成了更长的序列而当前‘a‘单独成序列的1与之前dp[‘a‘]所代表的那个“a“序列在赋值更新时旧的dp[‘a‘]被覆盖了。但这里覆盖的是“以‘a‘结尾的序列集合”而旧集合里的“a“和新加的“a“是同一个字符串所以覆盖操作实际上起到了去重作用。结论对于“非递减”情况算法依然有效只需将内层循环的条件从c (ch - ‘a‘)改为c (ch - ‘a‘)。即允许小于等于当前字符的序列来接上它。算法的去重逻辑依然成立。7.2 如果字符串包含大写字母或数字如果字符集变大比如包含大小写字母和数字我们的dp数组大小就需要相应调整。例如如果包含‘0‘~‘9‘ ‘A‘~‘Z‘ ‘a‘~‘z‘总共有62个字符。我们依然可以开辟一个大小为62的数组并建立字符到索引的映射关系。算法框架完全不变只是内层循环求和的范围是[0, idx(ch)-1]。时间复杂度变为 O(62 * n)依然是线性完全可行。7.3 如何输出具体的序列本题只要求计数但有时我们可能需要输出所有序列。虽然这在组合爆炸时不可能但对于小规模字符串或作为理解辅助是有用的。我们可以修改dp数组让它存储一个字符串集合如vectorstring但这样空间和时间开销极大。更高效的做法是结合回溯和DP计数进行剪枝或者使用自动机相关的数据结构但这已远超本题范围。在竞赛中99%的情况只要求计数。7.4 与其他DP问题的联系这道题的本质是一个线性DP其状态设计巧妙地利用了“结尾字符”这一维度将指数级的问题降维到了常数级26维。它和经典的“最长上升子序列LIS”问题在思想上有相通之处但LIS求的是长度最大值用的是“以某个位置结尾”的状态而本题求的是方案总数并且需要去重所以必须使用“以某个字符结尾”的状态。这也提醒我们在解决计数类DP问题时状态的定义要直接面向“结果”的特征如最后一个字符而不是面向“过程”的中间状态如原串中的位置这样可以更有效地合并重复状态。8. 常见错误与调试记录在我自己学习和教学过程中学生们常犯以下几个错误错误使用累加将dp[ch] new_count写成dp[ch] new_count。这会导致对于重复字符其贡献被多次计算结果远大于正确答案。症状对于“aa“这样的输入结果不是1而是2或更多。求和范围错误内层循环条件写错例如写成c (ch - ‘a‘)来求严格递增序列这会把相等字符的序列也加进来导致结果偏大。数据类型溢出使用int导致结果错误。症状对于较长的全递增字符串程序输出负数或一个明显偏小的正数。忽略空序列题目明确要求非空但结果加了1或者题目没明确自己默认加了1导致错误。一定要仔细审题。初始化错误将dp数组初始化为1认为每个字符自身就是一个序列。这看起来合理但在后续更新new_count 1 sum_less时这个1就重复计算了。正确的初始化是0因为new_count中的1已经包含了自身成序列的情况。调试建议在纸上用一个小例子如“aba“手动模拟你的算法画出dp数组每一步的变化。在代码中添加打印语句在每次更新dp[ch]时输出chsum_lessnew_count以及更新后的dp数组。编写一个暴力DFSSet的验证函数用于测试长度小于等于10的字符串确保你的DP结果与暴力结果完全一致。这道“本质上升序列”题从看似简单的描述中提炼出了一个精妙的状态定义和去重思想。它考察的不仅仅是对DP模板的记忆更是对问题本质的洞察力和抽象能力。掌握它你不仅能够解决蓝桥杯的这一道真题更能将这种“以结尾字符分类”的计数DP思想应用到其他字符串去重计数问题中真正做到举一反三。在竞赛的考场上遇到类似的题目你就能快速识别模型稳准狠地拿下分数。 
长河君 · 2026/8/28 7:58:13 · 阅读 1.2k 蓝桥杯动态规划难题解析：本质上升序列计数与去重
1. 项目概述一道经典的动态规划“计数”难题如果你刷过蓝桥杯国赛的真题尤其是C/C B组那么“本质上升序列”这道题绝对是一个绕不开的坎。它不像某些题目那样一眼就能看出是DFS或者贪心这道题的核心在于“计数”而且计的是“本质不同”的序列数量。乍一看题目描述可能并不复杂给定一个字符串要求计算出其所有“本质不同”的上升子序列的数量。但就是这个“本质不同”让无数选手在赛场上挠头也让这道题成为了区分算法功底深浅的试金石。我当年第一次碰到这道题时也陷入了思维定式试图用回溯去重结果复杂度直接爆炸。后来静下心来结合动态规划和集合论的思想才真正理解了其精妙之处。这道题完美地融合了字符串处理、动态规划状态定义以及去重逻辑是提升对DP理解深度的绝佳材料。它不仅考察你会不会写状态转移方程更考察你能否精准地定义“状态”来规避重复计数。无论是备战蓝桥杯还是希望夯实动态规划基础吃透这道题都能让你受益匪浅。2. 核心概念解析什么是“本质上升序列”要解决这个问题我们必须先掰开揉碎彻底理解题目的每一个约束条件。这不仅仅是读懂题更是为后续设计算法打下坚实的基础。2.1 问题重述与定义题目通常这样描述给定一个全部由小写字母构成的字符串s例如lanqiao我们需要找出其所有的“本质不同的上升子序列”。这里的术语需要逐一明确子序列由原字符串在不改变字符相对顺序的情况下删除某些字符也可以不删除后形成的新序列。例如对于abca,ab,ac,bc,abc都是它的子序列。空序列通常也被认为是子序列但在此类计数问题中需要根据题目要求确认是否计入。上升在此题语境下“上升”指的是子序列中每个字符的ASCII码值单调递增。也就是说对于子序列s[i1], s[i2], ..., s[ik]必须满足i1 i2 ... ik且s[i1] s[i2] ... s[ik]。注意是严格递增不是非递减。本质不同这是本题最大的难点。两个子序列如果其构成的字符串完全相同则它们被视为同一个即“本质相同”。例如字符串aba中选取第一个和第三个字符‘a‘, ‘a‘形成的子序列aa与选取第二个和第三个字符‘b‘, ‘a‘不这不符合上升规则。我们换一个例子abab。考虑上升子序列ab。它可以通过选取索引 (0,1) 的字符得到也可以通过选取索引 (0,3) 的字符得到因为‘a‘‘b‘且索引03。虽然来自原字符串的不同位置但形成的序列都是ab因此它们只被计数一次。所以题目的最终目标就是统计给定字符串s中所有字符严格递增的、且字符串表示互不相同的子序列的个数。2.2 一个简单的例子让我们用s abc这个最简单的例子来直观感受一下。 所有可能的、字符严格递增的子序列有长度为1a,b,c(3个)长度为2ab,ac,bc(3个)长度为3abc(1个) 总数为 331 7。由于abc中每个字符都唯一所以这里所有序列自然就是“本质不同”的。答案就是7。再看一个稍复杂的例子s aba。 我们需要找出所有严格递增的子序列长度为1a,b,a。注意这里有两个a但它们来自字符串的不同位置索引0和索引2。根据“本质不同”的定义它们形成的字符串都是a所以只能算1个。因此长度为1的本质不同子序列是{a “b“}共2个。长度为2 可能的有“ab“(索引0,1) 和“ab“(索引0,2)? 等等索引(0,2)是‘a‘, ‘a‘不满足严格递增。那么“ba“(索引1,2) 呢‘b‘ ‘a‘也不满足。所以唯一满足递增的只有“ab“(索引0,1)。长度为2的本质不同子序列只有{ab“}共1个。长度为3“aba“不满足严格递增。 因此对于“aba“答案是 2 1 3。通过这两个例子我们应该能清晰感受到“本质不同”的要求意味着我们不能简单地枚举所有索引组合然后判断是否上升因为那样会重复计数相同的字符串。我们必须以一种能够自动合并相同结果的方式进行计数。3. 暴力思路与瓶颈为什么不能直接枚举拿到问题最朴素的想法就是生成字符串的所有子序列检查每个子序列是否严格上升最后用一个集合如setstring来存储满足条件的子序列的字符串形式集合的大小就是答案。这个思路的代码如下C示意#include iostream #include set #include string using namespace std; void dfs(const string s, int index, string current, setstring result) { if (index s.length()) { if (current.length() 0) { // 非空子序列 // 检查current是否严格上升 bool isIncreasing true; for (int i 1; i current.length(); i) { if (current[i] current[i-1]) { isIncreasing false; break; } } if (isIncreasing) { result.insert(current); // 利用set去重 } } return; } // 不选当前字符 dfs(s, index 1, current, result); // 选当前字符 current.push_back(s[index]); dfs(s, index 1, current, result); current.pop_back(); } int main() { string s “lanqiao“; // 示例字符串 setstring res; string cur; dfs(s, 0, cur, res); cout res.size() endl; return 0; }这个方法的致命缺陷是什么时间复杂度。一个长度为n的字符串其子序列总数高达2^n个每个字符选或不选。当n较大时比如蓝桥杯真题中长度可能达到200甚至更多2^200是一个天文数字完全无法在限定时间内通常1秒完成计算。因此暴力枚举集合去重的路径是行不通的。我们必须寻找一种更高效、无需显式生成所有子序列就能完成“计数”和“去重”的方法。注意这里有一个关键点即使我们优化检查过程比如在DFS过程中维护当前序列的最后一个字符保证加入新字符时是递增的我们仍然需要遍历指数级的搜索空间并承受set插入和比较字符串的巨大开销。对于算法竞赛这绝对是下策。4. 动态规划DP的核心思路拆解既然不能枚举所有子序列我们就必须用动态规划来“数”出这个结果。DP的精髓在于利用已解决的子问题来构建当前问题的解避免重复计算。对于此题我们需要设计一个状态它既能表征“以某个位置结尾”的信息又能巧妙地处理“本质不同”的去重。4.1 状态定义的探索与确定最直接的想法之一是定义dp[i]表示以字符串中第i个字符s[i]作为最后一个字符的、严格上升的本质不同子序列的个数。这个定义初看有点道理但我们试着用它来思考转移。对于dp[i]我们如何从j i的状态dp[j]转移过来条件是s[j] s[i]。那么dp[i]似乎应该等于所有满足s[j] s[i]的dp[j]之和再加上字符s[i]自身作为一个长度为1的子序列的情况即1。但这里有一个巨大的问题重复计数。 考虑字符串s “abab“。我们计算dp[3](以最后一个‘b‘结尾)。j0:s[0]‘a‘ ‘b‘,dp[0]代表以第一个‘a‘结尾的子序列数假设我们正确计算了dp[0]1(只有“a“)。那么dp[0]的这些子序列后面加上‘b‘会得到“ab“。j2:s[2]‘a‘ ‘b‘,dp[2]代表以第三个字符‘a‘结尾的子序列数。关键来了在s[0…2]“aba“这个子串中以第二个‘a‘结尾的本质不同上升子序列有哪些它自己“a“是一个。但是这个“a“和以第一个‘a‘结尾的“a“是“本质相同”的如果我们简单地把dp[2]也加进来那么由dp[2]1贡献的“a“ ‘b‘得到的“ab“就和由dp[0]贡献的“ab“重复了。所以简单的dp[i] 1 sum(dp[j]) for j i and s[j] s[i]会导致对于相同字符结尾的子序列其贡献被重复累加进而使得以其为前缀构建的更长子序列也被重复计数。正确的状态定义需要能区分以字符‘x‘结尾且这个‘x‘是字符串中“最后一次出现”的‘x‘吗不我们需要更根本的解决。4.2 基于字符集的状态定义与去重原理为了从根本上避免重复我们必须改变视角。既然“本质不同”关心的是最终的字符串是什么那么我们就应该以“子序列的最后一个字符是什么”作为状态划分的依据而不是“以原字符串中第几个字符结尾”。定义dp[c]表示当前所有以字符c结尾的、本质不同的严格上升子序列的个数。这里c的范围是小写字母‘a‘到‘z‘。现在我们按顺序遍历原字符串s的每一个字符s[i]。对于当前遍历到的字符ch s[i]我们思考如何更新整个dp数组。更新逻辑如下对于字符ch本身它可以作为一个全新的、长度为1的子序列。所以dp[ch]至少应该增加1。更重要的是对于所有 ASCII 码小于ch的字符c‘所有以c‘结尾的现有子序列在其末尾追加当前字符ch后都能形成一个新的、以ch结尾的、且严格上升的子序列。并且由于我们是从所有以c‘结尾的子序列扩展而来而dp[c‘]已经保证了这些子序列彼此“本质不同”那么扩展后得到的以ch结尾的新子序列也一定是“本质不同”的。如何更新我们不能简单地dp[ch] dp[c‘]因为dp[ch]本身可能已经包含了一些子序列来自之前对ch的处理。我们需要的是以当前这个s[i]作为子序列最后一个字符的新序列数量。这个数量等于1 sum(dp[c‘]) for all c‘ ch。这里的1代表ch自身单独成序列。关键的去重操作但是请注意s[i]这个字符可能在字符串前面已经出现过。例如在“aba“中当i2遇到第二个‘a‘时如果我们只是计算new_sequences_for_this_a 1 sum(dp[c‘] for c‘ ‘a‘)由于没有字符小于‘a‘所以new_sequences_for_this_a 1。如果我们把这个1直接加到dp[‘a‘]上那么dp[‘a‘]就会变成2这代表了{“a“ (from index0), “a“ (from index2)}但它们是本质相同的这就重复了。所以正确的做法是对于当前字符ch我们计算出一个“新增量”add 1 sum(dp[c‘]) for c‘ ch。然后我们将dp[ch]直接更新为这个add而不是累加。为什么 因为dp[ch]记录的是“以字符ch结尾的本质不同子序列”。当我们在字符串中再次遇到字符ch时之前以ch结尾的子序列由更早出现的ch生成已经记录在dp[ch]里了。现在这个新出现的ch它可以和所有小于它的字符结尾的子序列结合形成新的一批以ch结尾的子序列。同时它自己单独也是一个。这两部分合起来就是“到当前位置为止所有以字符ch结尾的本质不同子序列”。而之前旧的dp[ch]值由更早的ch生成的那些序列实际上可以被当前这个新的、更全面的集合所覆盖。因为对于后续大于ch的字符来说它们可以接在任何一个以ch结尾的序列后面无论这个序列是由第一个ch还是第二个ch参与构成的只要序列字符串相同就是同一个。所以我们必须用最新的、最全的集合来代表dp[ch]。简单来说dp[ch] 1 sum(dp[c‘]) for c‘ ch每次遇到字符ch都执行这个赋值操作而不是。4.3 算法流程与示例演算让我们用s “aba“来完整走一遍这个DP过程。dp[26]数组初始全为0。处理s[0] ‘a‘计算add 1 sum(dp[c‘] for c‘ ‘a‘)。小于‘a‘的字符没有所以sum 0。add 1。更新dp[‘a‘] add 1。 此时dp[‘a‘]1表示以‘a‘结尾的序列有{“a“}。dp状态dp[‘a‘]1 其他为0。处理s[1] ‘b‘计算add 1 sum(dp[c‘] for c‘ ‘b‘)。小于‘b‘的字符有‘a‘。sum dp[‘a‘] 1。add 1 1 2。更新dp[‘b‘] add 2。 这2个序列是{“b“ “ab“}。其中“ab“是由dp[‘a‘]中的“a“后面加‘b‘得到的。dp状态dp[‘a‘]1dp[‘b‘]2。处理s[2] ‘a‘计算add 1 sum(dp[c‘] for c‘ ‘a‘)。sum 0。add 1。更新dp[‘a‘] add 1。 注意这里是赋值不是累加。所以dp[‘a‘]从1变成了1。这个新的1代表的是以当前这个‘a‘字符串末尾的‘a‘结尾的本质不同子序列。它包含了“a“自己。那之前以第一个‘a‘结尾的“a“呢它们本质相同所以被覆盖/替换了。此时dp[‘a‘]1仍然只表示{“a“}这一个序列成功去重dp状态dp[‘a‘]1dp[‘b‘]2。最终答案遍历所有字符c将dp[c]累加起来。ans dp[‘a‘] dp[‘b‘] 1 2 3。这与我们之前手动计算的结果一致。再验证一个例子s “abab“。i0,‘a‘:dp[‘a‘]1。 ({“a“})i1,‘b‘:add 1 dp[‘a‘]2。dp[‘b‘]2。 ({“b“ “ab“})i2,‘a‘:add 1。dp[‘a‘]1。 (覆盖仍然是{“a“})i3,‘b‘:add 1 dp[‘a‘]2。dp[‘b‘]2。 (注意这里把dp[‘b‘]更新为2而不是224。这2代表的是以当前这个‘b‘结尾的新序列集合{“b“ “ab“}。它和之前dp[‘b‘]表示的集合完全一样因为“a“后面接‘b‘得到的还是“ab“。)最终ans dp[‘a‘] dp[‘b‘] 1 2 3。 我们手动列举一下长度为1:“a““b“长度为2:“ab“。总共3个。正确。5. 代码实现与逐行解析理解了上述原理代码实现就非常清晰了。以下是完整的C实现#include iostream #include string #include vector using namespace std; int countDistinctIncreasingSubsequences(const string s) { // dp数组对应26个小写字母。dp[0]代表‘a‘ dp[25]代表‘z‘。 vectorlong long dp(26, 0); // 遍历字符串中的每一个字符 for (char ch : s) { // 计算所有小于当前字符的dp值之和 long long sum_less 0; for (int c 0; c (ch - ‘a‘); c) { sum_less dp[c]; } // 当前字符能形成的、以它结尾的新子序列数量 1自己 sum_less long long new_count 1 sum_less; // 关键直接赋值而不是累加以实现去重 dp[ch - ‘a‘] new_count; } // 统计所有以任意字符结尾的本质不同上升子序列总数 long long total 0; for (long long num : dp) { total num; } return total; } int main() { string s; // 假设输入字符串例如蓝桥杯真题可能是 “tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl“ // 这里用简单例子测试 s “lanqiao“; int result countDistinctIncreasingSubsequences(s); cout result endl; return 0; }代码关键点解析数据类型使用long long。因为结果可能非常大远超int范围。蓝桥杯国赛的数据规模往往要求使用64位整数。dp数组初始化大小为26初始值为0。dp[i]表示以字符(char)(‘a‘i)结尾的本质不同上升子序列的个数。核心循环for (char ch : s)顺序遍历字符串。顺序至关重要它保证了我们构造子序列时字符的相对顺序与原串一致。内层循环for (int c 0; c (ch - ‘a‘); c)计算所有ASCII码小于当前字符ch的dp值之和即sum_less。这代表了所有可以接上当前字符ch形成更长上升子序列的“基础序列”数量。new_count 1 sum_less1是当前字符自成序列sum_less是所有小于它的字符结尾的序列后面追加它。这两部分合起来就是以当前这个位置的ch作为序列结尾能形成的所有新序列。dp[ch - ‘a‘] new_count这是去重的灵魂。直接赋值意味着我们只关心“到最后一次出现字符ch的位置为止”以ch结尾的序列有哪些。之前的记录被覆盖因为对于后续字符来说它们只需要知道以ch结尾的序列集合是什么而不关心这个集合是由哪个ch产生的。最终求和遍历dp数组将所有值相加即为所有可能的、非空的、本质不同的严格上升子序列总数。复杂度分析时间复杂度O(26 * n)其中 n 是字符串长度。因为对于每个字符我们最多需要累加26个dp值。这是一个非常高效的线性算法。空间复杂度O(26)即常数空间。6. 边界情况、陷阱与实战技巧即使理解了算法在竞赛中实现时也可能踩坑。下面是一些必须注意的细节和提升代码鲁棒性的技巧。6.1 空序列是否计入这是一个必须明确的边界条件。题目描述有时会明确说明“非空子序列”。在我们的算法中dp值计算时包含了每个字符自身1所以最终求和total是包含了所有非空子序列的。如果题目要求包含空序列只需要在最终结果上加1即可。但根据蓝桥杯历年真题的惯例和“上升”的定义空序列通常不被认为具有“上升”属性默认不包含空序列。在比赛时务必仔细阅读题目的输出描述。6.2 大整数溢出问题这是本题最大的陷阱之一。字符串长度可能达到200本质不同的上升子序列数量可以非常庞大。例如对于一个完全递增的字符串“abcdefghijklmnopqrstuvwxyz“其本质不同上升子序列数等于所有非空子集数即2^26 - 1约等于6.7亿还在int范围内。但如果字符串更长或者字符集更集中导致组合更多结果很容易超出int甚至long的范围。在C/C中long在Windows平台通常是4字节和int一样。因此必须使用long long64位整数来存储dp值和最终结果。这是国赛题目的常见考点。6.3 初始化与更新顺序dp数组初始化为0是没问题的。更新顺序就是字符串的遍历顺序这符合子序列的定义。内层循环求sum_less时必须严格遍历所有小于当前字符的索引。这里不能优化成维护一个前缀和数组吗理论上可以但考虑到字母只有26个直接遍历的代价极小且逻辑清晰不易错竞赛中完全足够。6.4 测试用例设计自己编写代码后一定要用多种用例测试简单用例“a“- 1“ab“- 3“aa“- 1“aba“- 3。全递增长串“abcde“-2^5 - 1 31。可以用组合数学验证长度为k的严格递增子序列有C(5, k)个总和为C(5,1)C(5,2)…C(5,5)31。全相同串“aaaa“- 1。因为只有“a“这一种子序列。复杂串“abab“- 3“acbac“可以手动计算验证。最大规模随机测试生成长度200的随机字符串用你的DP代码和一个暴力DFSSet的代码仅用于小规模验证如n15进行对拍确保结果一致。实操心得在竞赛中对于这种计数DP我习惯在写完代码后立刻用最小的例子如“a“和全相同例子如“aaa“测试这两个例子往往能快速暴露初始化或更新逻辑的错误。7. 算法扩展与思维提升解决这个问题后我们不妨思考一些相关的变种或更深层次的问题这能极大锻炼我们的算法思维。7.1 如果求“非递减”子序列呢将条件从“严格递增” () 改为“非递减” ()即允许相等字符出现在子序列中。此时状态定义和转移需要如何调整核心矛盾在于去重。对于“aa“非递减子序列有“a“,“a“,“aa“。其中两个“a“本质相同。如果沿用之前的dp[ch] new_count赋值法当处理第二个‘a‘时new_count 1 sum(dp[c‘] for c‘ ‘a‘)注意这里条件变成了c‘ ‘a‘那么sum就包含了dp[‘a‘]自身来自第一个‘a‘。new_count 1 dp[‘a‘] 112。这表示以当前这个‘a‘结尾的新序列有“a“(自己) 和“aa“(由之前的“a“接上当前‘a‘)。而dp[‘a‘]被更新为2。最终所有dp值求和时dp[‘a‘]2代表了{“a“ “aa“}。咦我们发现两个“a“被成功地合并为了一个。这是因为在计算当前‘a‘的new_count时我们加上了之前dp[‘a‘]这相当于把“以前一个‘a‘结尾的序列”后面再追加一个‘a‘从而形成了更长的序列而当前‘a‘单独成序列的1与之前dp[‘a‘]所代表的那个“a“序列在赋值更新时旧的dp[‘a‘]被覆盖了。但这里覆盖的是“以‘a‘结尾的序列集合”而旧集合里的“a“和新加的“a“是同一个字符串所以覆盖操作实际上起到了去重作用。结论对于“非递减”情况算法依然有效只需将内层循环的条件从c (ch - ‘a‘)改为c (ch - ‘a‘)。即允许小于等于当前字符的序列来接上它。算法的去重逻辑依然成立。7.2 如果字符串包含大写字母或数字如果字符集变大比如包含大小写字母和数字我们的dp数组大小就需要相应调整。例如如果包含‘0‘~‘9‘ ‘A‘~‘Z‘ ‘a‘~‘z‘总共有62个字符。我们依然可以开辟一个大小为62的数组并建立字符到索引的映射关系。算法框架完全不变只是内层循环求和的范围是[0, idx(ch)-1]。时间复杂度变为 O(62 * n)依然是线性完全可行。7.3 如何输出具体的序列本题只要求计数但有时我们可能需要输出所有序列。虽然这在组合爆炸时不可能但对于小规模字符串或作为理解辅助是有用的。我们可以修改dp数组让它存储一个字符串集合如vectorstring但这样空间和时间开销极大。更高效的做法是结合回溯和DP计数进行剪枝或者使用自动机相关的数据结构但这已远超本题范围。在竞赛中99%的情况只要求计数。7.4 与其他DP问题的联系这道题的本质是一个线性DP其状态设计巧妙地利用了“结尾字符”这一维度将指数级的问题降维到了常数级26维。它和经典的“最长上升子序列LIS”问题在思想上有相通之处但LIS求的是长度最大值用的是“以某个位置结尾”的状态而本题求的是方案总数并且需要去重所以必须使用“以某个字符结尾”的状态。这也提醒我们在解决计数类DP问题时状态的定义要直接面向“结果”的特征如最后一个字符而不是面向“过程”的中间状态如原串中的位置这样可以更有效地合并重复状态。8. 常见错误与调试记录在我自己学习和教学过程中学生们常犯以下几个错误错误使用累加将dp[ch] new_count写成dp[ch] new_count。这会导致对于重复字符其贡献被多次计算结果远大于正确答案。症状对于“aa“这样的输入结果不是1而是2或更多。求和范围错误内层循环条件写错例如写成c (ch - ‘a‘)来求严格递增序列这会把相等字符的序列也加进来导致结果偏大。数据类型溢出使用int导致结果错误。症状对于较长的全递增字符串程序输出负数或一个明显偏小的正数。忽略空序列题目明确要求非空但结果加了1或者题目没明确自己默认加了1导致错误。一定要仔细审题。初始化错误将dp数组初始化为1认为每个字符自身就是一个序列。这看起来合理但在后续更新new_count 1 sum_less时这个1就重复计算了。正确的初始化是0因为new_count中的1已经包含了自身成序列的情况。调试建议在纸上用一个小例子如“aba“手动模拟你的算法画出dp数组每一步的变化。在代码中添加打印语句在每次更新dp[ch]时输出chsum_lessnew_count以及更新后的dp数组。编写一个暴力DFSSet的验证函数用于测试长度小于等于10的字符串确保你的DP结果与暴力结果完全一致。这道“本质上升序列”题从看似简单的描述中提炼出了一个精妙的状态定义和去重思想。它考察的不仅仅是对DP模板的记忆更是对问题本质的洞察力和抽象能力。掌握它你不仅能够解决蓝桥杯的这一道真题更能将这种“以结尾字符分类”的计数DP思想应用到其他字符串去重计数问题中真正做到举一反三。在竞赛的考场上遇到类似的题目你就能快速识别模型稳准狠地拿下分数。