1. 问题引入从“上升序列”到“本质不同”最近在复盘蓝桥杯国赛的真题翻到了2020年第十一届C/C大学A组的这道“本质上升序列”。题目本身描述很简洁给定一个字符串要求计算其所有“本质不同”的“上升子序列”的个数。很多同学第一眼看到“上升子序列”会立刻联想到经典的“最长上升子序列”LIS动态规划问题但仔细一看这里的“上升”指的是字符串中字符的字典序递增而“本质不同”则意味着即使子序列内容相同只要在原字符串中的位置下标不同就算作不同的序列。这和我们平时处理子序列问题的思路有很大不同不是求最长而是求所有不重复的、满足特定条件的子序列的数量。这种计数类动态规划问题在算法竞赛中非常考验对状态定义和转移方程的理解深度稍有不慎就会重复计数或者漏算。我记得当时第一次看到这题心里咯噔一下因为常规的LIS动态规划数组dp[i]通常表示以第i个元素结尾的最长上升子序列长度转移时关注的是长度最大值。但这里要求的是数量并且是“本质不同”的数量直接套用模板肯定不行。我们需要设计一个新的状态来精确记录以某个字符结尾的、满足条件的所有不同子序列的数量同时还要避免因为同一个子序列可以通过不同路径形成而导致的重复计算。这其中的状态定义、转移逻辑和去重技巧正是这道题的核心价值所在也是动态规划思想从“最值问题”向“计数问题”拓展的一个典型范例。理解清楚这道题对于处理更复杂的序列计数问题比如带限制条件的子序列个数、不同子序列个数等都会有很大帮助。2. 核心概念拆解什么是“本质上升序列”在动手写代码之前我们必须把题目中的两个关键约束条件——“上升”和“本质不同”——彻底搞清楚。这直接决定了我们动态规划状态的定义。2.1 “上升”的字典序定义在这个问题里“上升”不是指数值大小而是指字符在字典序通常是ASCII码顺序上的严格递增。例如在字符串abc中子序列a,b,c,ab,ac,bc,abc都是上升的因为后一个字符的ASCII码大于前一个。而ba就不是因为ba不满足从前往后递增。这里有一个关键点空序列通常不计入除非题目特别说明我们一般从长度为1的序列开始考虑。2.2 “本质不同”的深刻含义这是本题最容易让人困惑的地方。“本质不同”不是指子序列的字符串内容不同而是指这些子序列在原始字符串中对应的下标序列不同。举个例子就明白了。假设字符串是aba。内容为a的子序列它可以由第一个字符a下标0形成也可以由第三个字符a下标2形成。虽然内容都是a但因为来自原字符串的不同位置所以这是两个“本质不同”的子序列。内容为ab的子序列它可以由 (下标0的a, 下标1的b) 形成。也可以由 (下标2的a, 下标1的b) 形成吗不行因为子序列要求下标递增下标2 下标1顺序不对。所以ab只有一种构成方式。内容为aa的子序列它可以由 (下标0的a, 下标2的a) 形成。它满足“上升”吗不满足因为a和a相等不是严格递增。所以aa不是合法的上升子序列。所以我们的动态规划状态必须要能区分出来自不同下标的、相同字符结尾的子序列。一个很自然的想法是用dp[i]表示以字符串中第i个位置下标i的字符结尾的、满足上升条件的本质不同子序列的数量。注意这里dp[i]包含了所有长度大于等于1、以s[i]结尾的合法子序列。2.3 与经典LIS问题的根本区别为了加深理解我们对比一下经典的LIS动态规划解法。对于数组arrdp_lis[i]通常表示以arr[i]结尾的最长上升子序列的长度。转移方程是dp_lis[i] max(dp_lis[j]) 1其中j i且arr[j] arr[i]。 它只关心最大值并且对于同一个i不同的j可能产生相同的dp_lis[i]值但这在求长度时没关系。在我们的问题中dp[i]表示数量。如果简单模仿可能会写出dp[i] sum(dp[j]) 1其中j i且s[j] s[i]。这里的1表示子序列只包含s[i]自身的情况。 这个思路方向是对的但存在一个巨大的隐患重复计数。3. 动态规划状态设计与重复计数陷阱直接使用dp[i] sum(dp[j]) 1会带来什么问题我们用一个稍复杂的例子abab来模拟一下。按照上述公式i0(s[0]a):dp[0] 1(只有a)i1(s[1]b):j可以取0因为a b。dp[1] dp[0] 1 1 1 2。这2个序列是b和ab。正确。i2(s[2]a): 找j 2且s[j] a。没有字符比a小ASCII码所以dp[2] 1(只有a这里指第二个a)。正确。i3(s[3]b): 找j 3且s[j] b即a。j可以是0和2。从j0转移过来意味着在所有以s[0](第一个a) 结尾的序列后面加上s[3](b)。以s[0]结尾的序列有a。得到新序列ab。从j2转移过来意味着在所有以s[2](第二个a) 结尾的序列后面加上s[3]。以s[2]结尾的序列有a。得到新序列ab。再加上s[3]自身形成的序列b。 按照公式dp[3] dp[0] dp[2] 1 1 1 1 3。但我们来手动枚举一下以第三个位置下标3第二个b结尾的本质不同上升子序列序列b(仅包含自身)序列ab(由下标0的a和 下标3的b构成)序列ab(由下标2的a和 下标3的b构成) --等等你会发现第2和第3条虽然来自不同的a但它们形成的子序列字符串都是ab。根据“本质不同”的定义我们需要的是下标序列不同。下标序列(0,3)和(2,3)确实是不同的。所以它们应该被算作两个不同的序列。那么dp[3]应该是3吗我们继续枚举。序列aab不可能因为a和a不满足严格上升。序列bab不可能起始b 后续a不满足递增。看起来dp[3]3是对的但我们再仔细看dp[1]它代表了以第一个b下标1结尾的序列b和ab下标0和1。注意这个ab的下标序列是(0,1)。现在考虑整个字符串abab。一个非常关键的陷阱出现了内容为ab的子序列在整个字符串中出现了多少次由下标 (0,1) 构成 -- 对应以s[1]结尾的序列之一。由下标 (0,3) 构成 -- 对应以s[3]结尾的序列之一。由下标 (2,3) 构成 -- 对应以s[3]结尾的另一个序列。所以ab这个内容在整个问题中对应了3个“本质不同”的子序列。它们被正确地分别记录在了dp[1]和dp[3]中。到目前为止我们的dp[i]定义和转移sum(dp[j]) 1似乎能正确区分来自不同结尾位置的相同内容子序列。但是更大的陷阱在后续转移中。假设字符串更长比如ababc。当我们计算以最后一个c结尾的dp[4]时我们需要把所有s[j] c的dp[j]加起来。这包括了dp[1]和dp[3]。那么对于ab这个内容从dp[1](ab(0,1)) 后面加c会得到abc(0,1,4)。从dp[3]中的第一个序列 (ab(0,3)) 后面加c会得到abc(0,3,4)。从dp[3]中的第二个序列 (ab(2,3)) 后面加c会得到abc(2,3,4)。看abc这个内容又通过三条不同的路径产生了。关键在于这三条路径产生的abc其下标序列(0,1,4),(0,3,4),(2,3,4)确实是互不相同的所以它们应该被算作三个不同的子序列。我们的dp[i] sum(dp[j]) 1的转移方式实际上是把以j结尾的所有不同子序列都接上i从而生成了一批新的、以i结尾的子序列。只要j不同即使生成的字符串内容相同也因为其“历史路径”即前缀的下标序列不同而被视为不同的新序列。这恰好符合“本质不同”的定义。因此dp[i] 1 sum(dp[j]) for all j i and s[j] s[i]这个状态转移方程对于计数“本质不同”的上升子序列是正确的。其中1代表子序列只包含s[i]自身的情况。最终答案就是所有dp[i]的和即所有以任意位置结尾的合法子序列数量之和。4. 算法实现详解与初始化细节理解了状态定义和转移方程我们就可以着手实现了。这里给出C的详细实现并解释每一个细节。4.1 数据结构与初始化我们使用一个一维数组dp长度等于字符串长度n。dp[i]的含义如前所述以字符串s[i]字符结尾的、所有本质不同的严格上升子序列的个数。 初始化时对于每个位置i至少有一个子序列就是只包含它自己。所以我们可以将每个dp[i]初始化为1。#include iostream #include string #include vector using namespace std; int main() { string s abab; // 示例字符串实际题目中字符串可能很长 int n s.length(); vectorlong long dp(n, 1); // 初始化为1每个字符本身构成一个长度为1的子序列 // 注意使用 long long因为结果可能很大4.2 核心转移过程接下来就是二重循环。对于每一个位置i我们遍历它之前的所有位置j(0 j i)。如果s[j] s[i]说明字符s[j]可以放在s[i]前面形成一个更长的上升子序列。那么所有以s[j]结尾的合法子序列共有dp[j]个在后面添加上s[i]就形成了新的、以s[i]结尾的子序列。所以我们需要把dp[j]加到dp[i]上。for (int i 0; i n; i) { for (int j 0; j i; j) { if (s[j] s[i]) { dp[i] dp[j]; } } }4.3 结果计算与输出最终我们要求的是整个字符串中所有本质不同的上升子序列的个数。根据定义这个数就是所有dp[i]的总和因为每个合法的子序列都有一个唯一的“结尾位置”。long long ans 0; for (int i 0; i n; i) { ans dp[i]; } cout 字符串 \ s \ 的本质不同上升子序列个数为: ans endl; return 0; }把代码组合起来对于s abab运行过程如下i0: dp[0]1i1: j0, s 0 s 1 - dp[1] dp[0] dp[1] 112i2: j0, s 0 不小于 s 2 j1, s 1 s 2 。无转移dp[2]1i3: j0, s 0 s 3 - dp[3] dp[0] dp[3]112 j1, 不满足 j2, s 2 s 3 - dp[3] dp[2] dp[3]213。ans dp[0]dp[1]dp[2]dp[3] 1213 7。我们可以手动验证一下字符串abab的所有本质不同上升子序列 长度为1:a(pos0), b(pos1), a(pos2), b(pos3)- 4个 长度为2:ab(0,1), ab(0,3), ab(2,3)- 3个 (注意aa,bb不上升) 长度为3:aba? 不上升abb? 不上升aab? 不上升。实际上以b结尾的长度为3的序列需要前面有两个递增字符。ab后面接b不行bb。所以没有长度为3的合法序列。 总数为437与程序结果一致。4.4 一个关键的优化点去重不是理解网上有些关于这道题的讨论会提到“去重”的问题。他们指的是另一种重复当字符串中存在相同字符时直接累加dp[j]可能会导致以相同字符结尾的子序列被重复转移。考虑字符串abbi0: dp[0]1 (a)i1: j0, s 0 s 1 - dp[1] 1 dp[0] 2 (b,ab)i2: j0, s 0 s 2 - dp[2] dp[0] dp[2]112 j1, s 1 不小于 s 2 。所以 dp[2]2。 最终 ans 1225。 枚举验证a(0), b(1), b(2), ab(0,1), ab(0,2)。确实是5个。这里ab出现了两次对应下标(0,1)和(0,2)是本质不同的。那“重复”的担忧是什么假设字符串是abbb。计算dp[3]最后一个b时它会累加dp[0],dp[1],dp[2]。而以s[1]和s[2]结尾的子序列集合中都包含了由s[0]转移过来的ab。当它们再分别转移到dp[3]时会不会产生重复的abb序列我们来思考从dp[1]的ab(0,1)转移到dp[3]生成abb(0,1,3)。从dp[2]的ab(0,2)转移到dp[3]生成abb(0,2,3)。 这是两个下标序列不同的子序列(0,1,3)和(0,2,3)所以是合法的两个不同序列不是重复。我们的累加逻辑是正确的。所以对于“本质不同”的定义我们不需要在转移时对相同字符做特殊去重。真正的重复只会发生在完全相同的下标序列通过不同路径被生成多次。而在我们的状态定义dp[i]以位置i结尾和转移方程从所有满足条件的j转移过来下每一条路径生成的下标序列都是唯一的因此不会产生这种重复。5. 复杂度分析与算法优化上述解法的时间复杂度是 O(n²)空间复杂度是 O(n)。对于蓝桥杯竞赛环境如果字符串长度n达到 2000 左右O(n²) 的算法约400万次运算通常是可接受的。但如果我们追求更优的解法或者应对更大的数据范围比如 n10^5就需要考虑优化。5.1 O(n²) 算法的瓶颈瓶颈在于内层循环对于每个i都要遍历所有j i来找到满足s[j] s[i]的位置并累加dp[j]。这本质上是一个前缀和问题我们需要快速求出所有在i之前、且字符小于s[i]的位置的dp值之和。5.2 优化思路基于字符集的动态规划注意到字符集通常是有限的比如小写字母只有26个。我们可以维护一个辅助数组sum[26]其中sum[k]表示到目前为止所有以字符 (ak) 结尾的合法子序列的总数。算法流程可以优化为 O(26*n)初始化dp[n]和sum[26]都为0。遍历字符串的每个位置i其字符为c s[i] - a。计算dp[i]它等于1自身 所有小于字符c的字符对应的sum值之和。因为sum[k]已经累积了所有以字符k结尾的子序列数这些序列后面加上s[i]都能形成新的、以s[i]结尾的序列。更新sum[c]将新计算出的dp[i]加到sum[c]上。因为现在以字符c结尾的子序列又多了一批新增了以当前位置i结尾的。最终答案就是sum[0] sum[1] ... sum[25]。C 优化实现如下#include iostream #include string #include vector using namespace std; int main() { string s; // 假设从输入读取字符串 s // cin s; s abab; int n s.length(); vectorlong long dp(n, 0); long long sum[26] {0}; // 记录以每个字符结尾的子序列总数 const int MOD 1000000007; // 如果结果需要取模题目常要求 for (int i 0; i n; i) { int cur_char s[i] - a; dp[i] 1; // 自身作为一个序列 for (int k 0; k cur_char; k) { dp[i] (dp[i] sum[k]) % MOD; // 累加所有更小字符的sum } // 更新以当前字符结尾的总数 sum[cur_char] (sum[cur_char] dp[i]) % MOD; } long long ans 0; for (int k 0; k 26; k) { ans (ans sum[k]) % MOD; } cout ans endl; return 0; }这个优化版本将内层循环的O(n)降为了O(26)总复杂度O(26*n)对于字母串处理效率极高。它同样正确地处理了“本质不同”的问题因为sum[k]累积的是所有以字符k结尾的dp值而每个dp[i]在计算时累加的是历史的所有sum[k]这些sum[k]已经包含了所有可能的历史路径。6. 边界条件、大数与实战注意事项在实际竞赛中处理此类计数问题还需要注意以下几点6.1 空序列是否计入题目描述通常会说“非空上升子序列”。我们的算法从dp[i]1开始计数的就是所有非空子序列。如果题目要求包含空序列只需要在最终结果上加1即可。务必仔细审题。6.2 结果的大数处理这类计数问题的结果往往非常巨大。比如一个长度为2000的完全递增字符串其本质不同上升子序列数量是一个天文数字。在C/C中必须使用long long64位整数。即便如此也可能溢出。蓝桥杯的题目有时会要求将结果对某个大数如1e97取模。这时我们在每一步加法运算后都应及时取模避免中间结果溢出。6.3 字符集范围我们的优化算法假设字符是小写字母。如果字符集更大比如包含大写字母、数字则sum数组的大小需要相应调整如128对应ASCII码。此时复杂度为O(m*n)其中m是字符集大小。如果字符集非常大如Unicode那么O(m*n)可能退化成O(n²)这时可能需要借助树状数组或线段树来维护前缀和将查询“小于当前字符的dp和”的复杂度降到O(log m)。6.4 调试与验证技巧对于动态规划计数问题最好的调试方法就是从小例子开始手动计算并和程序输出对比。像a,ab,aa,aba,abb,abc这样的短字符串完全可以手工枚举所有合法子序列确保算法逻辑正确。这也是理解问题本质的最佳途径。7. 举一反三与其他子序列计数问题的关联解完这道题我们可以将其思路推广到一系列子序列计数问题7.1 统计所有“不同子序列”个数LeetCode 115. 不同的子序列这是一道经典题给定字符串s和t计算s的子序列中等于t的个数。这里的“不同”指的是内容不同还是下标序列不同通常是下标序列不同。其动态规划定义dp[i][j]表示s的前i个字符中子序列等于t的前j个字符的个数。转移方程考虑s[i-1]是否等于t[j-1]。这和我们本题“以特定字符结尾”的思路有相通之处但状态是二维的因为要匹配目标串t。7.2 统计一个字符串的所有不同子序列个数不要求上升这个问题可以看作是本题的简化版去掉“上升”约束。我们可以定义dp[i]为以s[i]结尾的所有不同子序列个数。转移时需要加上所有j i的dp[j]。但这样会产生大量重复因为以相同字符结尾的不同子序列其前缀可能相同。标准的解法是定义dp[i]为考虑前i个字符时形成的所有不同子序列的个数不以i结尾。当遇到一个新字符s[i]时新增的子序列数量等于之前的dp[i-1]每个旧序列后面加上新字符但要减去上一次这个新字符出现时所对应的dp值避免重复。这需要记录每个字符上次出现时的贡献。7.3 带限制条件的上升子序列计数例如求长度恰好为k的上升子序列个数或者求上升子序列中相邻元素差值不超过d的个数。这些问题可以在我们dp[i]以i结尾的数量的基础上增加一维状态表示长度或其他属性变成dp[i][l]转移时在满足上升条件的同时还要满足长度或其他约束。通过解决“本质上升序列”这道题我们深入理解了基于下标序列唯一性的计数动态规划。其核心在于定义dp[i]为以位置i结尾的合法序列数并通过累加所有可能的前驱状态dp[j]来转移。对于字符集有限的情况利用前缀和思想可以大幅优化。掌握这个模型就能应对许多变种的子序列计数问题。在竞赛中清晰的思路和对“本质不同”的准确把握是快速解出此类题目的关键。