动态规划解决本质不同上升子序列计数：从状态定义到去重优化

1. 问题引入从一个看似简单的字符串问题说起最近在整理历年算法竞赛的经典题目时我又翻到了2020年蓝桥杯国赛C B组的那道“本质上升序列”。这道题当时卡住了不少人包括我自己第一次接触时也绕了不少弯路。题目描述很简单给定一个全部由小写字母构成的字符串要求计算其“本质不同的上升子序列”的个数。这里的“上升”指的是子序列中每个字符的ASCII码值严格递增。举个例子字符串lanqiao它的一个上升子序列可以是l、ln、lq等。但题目要求的是“本质不同”这意味着即使两个子序列由原字符串中不同位置的字符组成只要它们看起来一模一样字符序列相同就只能算作一个。比如在aba中选取第一个和第三个字符a组成的子序列a与只选取第一个字符a组成的子序列a是同一个不能重复计数。初看之下这似乎是一个标准的动态规划DP求不同子序列个数的问题只不过加了一个“字符递增”的约束。但如果你直接套用求所有不同子序列的模板或者用求最长上升子序列LIS的思路去硬解很快就会发现问题没那么简单。它巧妙地将“去重”和“有序”两个条件结合在一起对状态定义和转移逻辑的严谨性提出了很高的要求。今天我们就来彻底拆解这道题从最朴素的思路开始一步步推导到最优的DP解法并深入探讨其中的关键细节和易错点。2. 核心概念辨析什么是“本质不同的上升子序列”在动手写代码之前我们必须把题目中的几个关键概念掰开揉碎理解透彻。任何一点模糊都可能导致后续状态设计的偏差。2.1 子序列 (Subsequence) 与子串 (Substring)这是两个基础但必须严格区分的概念。子序列是从原字符串中删除零个或多个字符后保持剩余字符相对顺序所形成的序列。它不要求字符连续。例如lanqiao的子序列包括空序列、l、a、la、ln、lna等等数量是指数级的。而子串则要求是原字符串中连续的一段比如lan、anq。本题明确要求的是子序列因此我们的算法必须能处理非连续选取的情况。2.2 “上升”的含义基于ASCII码的严格递增题目中的“上升”并非指字母在字典序中的先后而是指字符的ASCII码值严格递增。小写字母a到z的ASCII码是97到122是连续递增的。因此abc... z这个关系是成立的。这意味着一个合法的上升子序列其字符从左到右必须满足越来越“大”。例如acf是合法的97, 99, 102而aca或ca则是不合法的。这个约束极大地限制了子序列的可能性。对于任意一个字符能接在它后面的字符范围是固定的ASCII码比它大的字符。2.3 “本质不同”的挑战去重是核心难点这是本题最精妙也最棘手的地方。我们不仅要计数还要对“看起来相同”的子序列进行去重。考虑字符串s abab。我们手动找一下以b结尾的长度为2的上升子序列选取s[1]第二个字符a和s[2]第三个字符b得到ab。选取s[1]第二个字符a和s[4]第五个字符b得到ab。选取s[3]第四个字符a和s[4]第五个字符b得到ab。虽然来源不同但它们都是ab。在我们的最终计数中ab只能算作1个。如果不去重单纯计算所有可能的上升子序列包括重复的会简单很多。但“本质不同”的要求迫使我们的状态设计必须能够自动规避重复计数或者在计数后进行去重操作。后者通常效率极低在竞赛中不可行。因此我们必须设计一种DP方法在转移过程中就保证每个“本质不同”的子序列只被计数一次。3. 从暴力枚举到动态规划的思路演进面对一个复杂问题我习惯先思考最直接的暴力方法明确问题的规模和解空间然后再寻找优化规律。3.1 暴力搜索的不可行性最暴力的方法是枚举原字符串的所有子序列然后检查每个子序列是否“上升”最后用一个集合Set来存储这些子序列的字符串表示集合的大小就是答案。对于一个长度为n的字符串其子序列总数高达2^n个。当n较大时比如蓝桥杯国赛的数据规模n可能达到200甚至更多2^200是一个天文数字完全无法计算。因此暴力枚举从理论上就被排除了。3.2 关键观察与DP状态定义我们需要利用动态规划来避免指数级的枚举。DP的核心思想是用一个状态来表示某个子问题的解并通过状态转移方程由小问题推导出大问题的解。对于子序列计数问题一个非常经典且有效的状态定义是dp[i]表示以第i个字符结尾的、满足某种条件的子序列的个数。在本题中“某种条件”就是“上升且本质不同”。让我们尝试定义dp[i]表示以字符串中第i个位置s[i]结尾的、本质不同的上升子序列的个数。这个定义看起来不错。那么dp[i]如何计算呢它应该由所有在i之前的位置j(j i) 转移而来前提是s[j] s[i]满足上升条件。我们可以把s[j]后面接上s[i]形成一个新的以s[i]结尾的子序列。但是这里有一个巨大的陷阱重复计数。 假设s aba我们计算dp[2]以最后一个a结尾。从j0(a) 转移s[0] s[2]不成立都是a不严格小于不能转移。从j1(b) 转移s[1] s[2](ba)不满足上升不能转移。那么以s[2]这个a本身作为一个长度为1的子序列呢它应该被计入dp[2]。所以我们需要初始化dp[i] 1代表只包含s[i]自身的子序列。现在考虑s abab计算dp[3]以最后一个b结尾。dp[3]初始为1 (b)。从j0(a) 转移a b成立。那么所有以s[0]结尾的子序列后面加上s[3]都能形成新的以s[3]结尾的子序列。所以dp[3] dp[0]。dp[0]是多少它是以第一个a结尾的子序列数初始为1 (a)。所以这次转移带来了子序列ab。从j1(b) 转移b b不成立不严格小于跳过。从j2(a) 转移a b成立。dp[3] dp[2]。dp[2]是以第二个a结尾的子序列数。这里问题来了dp[2]也包含了只包含它自身的子序列a。这次转移也会产生一个ab的子序列用第二个a和当前的b组成。我们发现通过j0和j2的转移我们两次得到了ab这个子序列。但根据“本质不同”的要求它只能被计数一次。我们之前的转移逻辑重复计数了3.3 解决重复计数的核心按字符最后出现位置转移问题的根源在于当存在多个相同的字符如a可以作为当前字符如b的前驱时这些相同的a会产生大量相同的子序列“ab”。如何保证每个“本质不同”的子序列只被算一次呢我们需要改变视角。对于一个最终的子序列比如“ab”决定它“本质”的是序列里的字符‘a’和‘b’。在原字符串中可能有多个‘a’和多个‘b’可以组成它。为了不重复一个巧妙的思路是我们强制规定在构造子序列时对于序列中每一个字符我们都只使用该字符在原字符串中“最后一次出现”的位置。为什么这样做可以保证不重不漏不漏对于任何一个“本质不同”的子序列我们总能在原字符串中找到一组位置构成它。如果这组位置不满足“每个字符取最后出现位置”我们可以把其中的字符替换成该字符最后出现的位置。由于是子序列只要替换后的位置顺序依然保持递增因为最后出现的位置肯定更靠后或不变那么它形成的字符串和原来是一样的。所以任何一个本质子序列都对应着一个“每个字符取最后出现位置”的构造方式。不重对于一种“每个字符取最后出现位置”的构造方式它产生的子序列字符串是唯一的。这样我们就把问题转化了我们不再关心字符所有可能出现的位置而是只关心每种字符最后出现的位置。计数时我们只从这些“最后出现的位置”进行转移。但这是一种思考方式直接实现起来有点抽象。我们可以将其转化为另一种等价的、更易于实现的状态定义。4. 正确的动态规划解法详解基于上面的分析我们设计出如下DP方案4.1 状态定义令dp[i]表示以字符s[i]结尾的、本质不同的上升子序列的个数。注意这里的i是字符在原字符串中的下标。4.2 转移方程与去重关键为了计算dp[i]我们需要考虑所有在i之前的、且字符小于s[i]的位置j(j i且s[j] s[i])。dp[i]应该加上这些dp[j]。但正如之前分析这会带来重复。重复来源于如果存在多个j满足s[j] ch同一个字符且ch s[i]那么从这些不同的j转移过来都会产生以ch开头、以s[i]结尾的相同子序列。解决办法是对于每一个字符ch在计算dp[i]时我们只考虑所有等于ch的j中dp[j]最大的那一个或者说只考虑最后一次出现的ch。实际上更精确的做法是我们维护一个辅助数组last[ch]记录字符ch上一次出现时计算出的dp值。在遍历字符串时我们动态更新这个值。具体步骤如下初始化一个长度为26的数组last初始值全为0。last[k]表示字符(‘a’k)在当前遍历过程之前所有以它结尾的本质不同上升子序列的总数。初始化一个数组dp长度等于字符串长度n。从左到右遍历字符串的每个位置i(从0开始) a. 对于当前字符s[i]它自身可以作为一个子序列所以dp[i]的初始值为1。 b. 我们需要把所有可以接在s[i]前面的子序列都算上。这些子序列的结尾字符必须小于s[i]。因此我们遍历所有比s[i]小的字符ch即 ASCII 码小于s[i]的字符。 c. 对于每一个这样的字符chlast[ch]就代表了在位置i之前所有以字符ch结尾的本质不同上升子序列的个数。把这些序列后面都加上s[i]就形成了新的以s[i]结尾的子序列。所以dp[i]需要加上last[ch]。 d. 用伪代码表示内层循环for (char ch ‘a’; ch s[i]; ch) dp[i] last[ch - ‘a’];e. 更新last数组在计算完dp[i]之后字符s[i]的“最后状态”发生了变化。我们需要将last[s[i] - ‘a’]更新为dp[i]。注意这里是累加还是赋值思考一下last[ch]应该记录的是“所有以字符ch结尾的本质不同子序列的总数”。当我们遇到一个新的s[i]时我们新产生了dp[i]个以s[i]结尾的子序列。但是之前可能已经有过以s[i]这个字符结尾的子序列了来自更早的位置。如果我们直接赋值last dp[i]就会覆盖掉之前的结果导致漏计。例如字符串“aa”第二个‘a’产生的子序列只有它自身“a”但如果直接赋值就会丢掉第一个‘a’产生的那个“a”。然而根据“本质不同”的要求这两个“a”是同一个所以我们不应该累加而应该赋值。因为last[s[i]]代表的是“以字符s[i]结尾的、所有本质不同子序列的总数”。当我们计算第二个‘a’时新产生的以‘a’结尾的子序列和之前产生的在“本质”上是完全重合的都是“a”。所以last[‘a’]的值应该就是dp[i]即最新计算出的以这个字符结尾的总数它已经包含了所有可能的情况。对于“aa”dp[0]1,last[‘a’]1计算dp[1]时因为‘a’不小于‘a’所以内层循环加不上任何东西dp[1]1然后last[‘a’]被更新为dp[1]1。总数是dp[0]dp[1]2但本质不同的上升子序列只有{“”, “a”}等等我们是不是漏了空序列题目通常要求计算非空子序列。我们暂时把空序列排除在外。那么对于“aa”本质不同的非空上升子序列确实只有{“a”}这一个。我们的dp数组求和得到2是因为我们把第一个‘a’和第二个‘a’当作不同的结尾位置分别计数了但它们对应的本质子序列是同一个。所以最终答案不能简单地将所有dp[i]相加。4.3 最终答案的获取由于dp[i]记录了以每个位置i结尾的子序列数并且我们的转移保证了“本质不同”只在字符层面去重但相同字符的不同位置仍然被独立计数了因为它们确实是不同的“结尾位置”尽管子序列字符串可能相同。为了得到整个字符串的本质不同上升子序列总数我们不能再对dp求和。正确的答案是遍历last数组将last[0]到last[25]的值全部加起来。因为last[ch]最终存储的就是以字符ch结尾的、所有本质不同的上升子序列的个数。它已经自动完成了对相同字符不同位置的去重。让我们用s “abab”来验证一下初始化last[26] {0},dp[4]。i0, s[0]‘a’:dp[0] 1(序列“a”)内层循环ch ‘a’不存在不加。更新last[‘a’] dp[0] 1。i1, s[1]‘b’:dp[1] 1(序列“b”)内层循环ch从‘a’到‘a’(即ch ‘b’):dp[1] last[‘a’] 1dp[1] 2(新增序列“ab”)更新last[‘b’] dp[1] 2。i2, s[2]‘a’:dp[2] 1(序列“a”)内层循环ch ‘a’不存在不加。更新last[‘a’] dp[2] 1。注意这里覆盖了之前的值1。i3, s[3]‘b’:dp[3] 1(序列“b”)内层循环ch从‘a’到‘a’:dp[3] last[‘a’] 1dp[3] 2(新增序列“ab”)更新last[‘b’] dp[3] 2。最终last[‘a’] 1,last[‘b’] 2。答案 last[‘a’] last[‘b’] 1 2 3。这3个本质不同的上升子序列分别是“a”,“b”,“ab”。你可以手动验证“abab”再也找不出第四个满足条件的子序列了“aa”,“bb”,“aba”,“abb”,“bab”等都不满足严格递增。4.4 算法复杂度分析设字符串长度为n字符集大小为C本题为26。我们遍历字符串一次复杂度 O(n)。在遍历每个字符时我们需要遍历所有比它小的字符最多25个进行累加操作。这是一个 O(C) 的操作。因此总时间复杂度为O(n * C)。由于 C26 是常数所以也可以认为是O(n)非常高效。空间复杂度为 O(C) 用于last数组以及 O(n) 用于dp数组实际上dp数组可以优化掉只用一个临时变量因为dp[i]计算完后只用于更新last后面不再使用。5. 代码实现与逐行解析以下是完整的C实现代码包含了详细的注释。#include iostream #include string #include vector using namespace std; int main() { string s; cin s; // 读入字符串 int n s.length(); // last数组记录以每个字符结尾的本质不同上升子序列的个数 // 下标0对应‘a’下标25对应‘z’ vectorlong long last(26, 0); // 遍历字符串的每一个字符 for (int i 0; i n; i) { char current_char s[i]; int idx current_char - a; // 当前字符对应的索引 // 步骤1: 计算以当前位置字符结尾的dp值 long long dp_i 1; // 字符自身构成一个子序列 // 步骤2: 累加所有可以接在当前字符前面的子序列 // 即累加所有ASCII码小于当前字符的 last[ch] for (int ch 0; ch idx; ch) { dp_i last[ch]; } // 步骤3: 更新last数组 // 注意这里是赋值不是累加。理由见上文分析。 last[idx] dp_i; } // 步骤4: 计算最终答案 // 将所有以某个字符结尾的子序列个数相加即为所有非空本质不同上升子序列的个数 long long ans 0; for (int i 0; i 26; i) { ans last[i]; } // 如果题目要求包含空序列则答案需要1。本题通常要求非空但需根据具体描述判断。 // 例如样例lanqiao的答案通常不包含空串。 // ans 1; // 如果包含空序列则加上这一行。 cout ans endl; return 0; }关键点解析数据类型long long子序列的数量可能非常庞大远超int的表示范围。例如一个由严格递增字母组成的字符串其本质不同上升子序列数是指数级的。必须使用long long或更高精度的整数类型。内层循环for (int ch 0; ch idx; ch)这里ch是字符的索引0到25循环条件ch idx完美对应了“所有比当前字符小的字符”。这是实现“上升”约束的核心。last[idx] dp_i;赋值操作这是实现“本质不同”去重的灵魂所在。它保证了对于同一个字符我们只保留最新即最后出现位置所产生的子序列集合总数。因为之前位置产生的相同字符结尾的子序列其“本质”已经被包含在最新的这个集合里了。最终答案的累加答案来自于last数组之和而不是dp数组之和。dp数组在计算过程中只是一个临时变量。6. 边界条件、易错点与测试用例即使理解了算法实现时也常常在细节上出错。下面是一些需要特别注意的点和测试用例。6.1 包含空序列吗这是一个必须明确的边界条件。题目描述有时会明确说明“非空子序列”有时默认包含空序列。在上述代码中我们计算的是非空的本质不同上升子序列。因为dp_i初始化为1代表字符自身这个序列。如果我们想包含空序列只需要在最终答案ans上加1即可。在竞赛中务必仔细阅读题目描述。对于2020年蓝桥杯国赛的这道题根据常见样例推断通常要求的是非空子序列。6.2 大整数溢出问题虽然我们使用了long long但如果字符串长度很大比如200且字符分布特殊答案仍然可能超出long long的范围大约9e18。例如一个长度为200的、完全严格递增的字符串如abc...z重复若干次但字母严格递增其本质不同上升子序列数量是2^200 - 1这远远超过了任何基本数据类型的范围。蓝桥杯的评测数据通常会控制在这个范围内但养成考虑数据范围的习惯很重要。在实际竞赛或工程中如果可能溢出需要使用高精度计算如C的__int128或自定义大整数类。6.3 测试用例验证我们来跑几个例子确保我们的代码和逻辑正确。用例1s “”(空字符串)代码会直接输出0。如果题目要求包含空序列则需要输出1。这里按非空处理输出0合理。用例2s “a”last[‘a’]最终为1。答案1。本质不同上升子序列{“a”}。用例3s “aa”如前所述last[‘a’]最终为1。答案1。序列{“a”}。用例4s “ab”i0 (‘a’):dp1,last[‘a’]1。i1 (‘b’):dp1last[‘a’]2,last[‘b’]2。答案 last[‘a’]last[‘b’]123。序列{“a”, “b”, “ab”}。用例5s “ba”i0 (‘b’):dp1,last[‘b’]1。没有比’b’小的字符可加i1 (‘a’):dp1,last[‘a’]1。没有比’a’小的字符可加答案 last[‘a’]last[‘b’]112。序列{“b”, “a”}。注意“ba”不是上升序列。用例6s “abc”这是一个严格递增的字符串。我们可以手动推导或运行程序。最终last[‘a’]1,last[‘b’]2,last[‘c’]4。答案1247。序列{“a”, “b”, “c”, “ab”, “ac”, “bc”, “abc”}。正好是2^3 - 1 7非空子集个数。对于严格递增字符串每个子序列都是上升的且本质不同。6.4 一个思维陷阱为什么不能对dp数组求和这是最常见的错误。让我们再用“abab”的例子看dp数组dp [1, 2, 1, 2]和为6。但正确答案是3。多出来的3个从哪里来的它们分别是第一个‘a’、第二个‘b’和第二个‘a’、第三个‘b’作为结尾位置时被重复计算的“a”,“b”,“ab”。dp数组记录的是“以某个位置结尾”的计数而题目要求的是“本质不同”的字符串与位置无关。last数组通过字符维度进行聚合自然完成了去重。7. 算法优化与空间压缩上面的代码已经非常高效但我们可以进行一些微小的优化使其更简洁并减少空间使用。7.1 优化掉dp数组注意到dp_i只在计算当前字符时使用并且用完后立即更新到last数组中之后不再需要。因此我们完全可以只用一个临时变量current_count来代替整个dp数组。#include iostream #include string #include vector using namespace std; int main() { string s; cin s; vectorlong long last(26, 0); for (char c : s) { int idx c - a; long long current_count 1; // 代表字符c自身作为一个子序列 for (int ch 0; ch idx; ch) { current_count last[ch]; } last[idx] current_count; // 关键赋值更新 } long long ans 0; for (long long val : last) { ans val; } cout ans endl; return 0; }这样空间复杂度从 O(n) 降到了 O(1) 的临时变量加上 O(26) 的last数组。7.2 处理包含空序列的情况如果题目要求包含空序列只需要在输出前给ans加1。但更好的做法是在逻辑上保持一致我们可以在初始化last数组时或者在一开始就把空序列算进去。不过最清晰的做法还是在最后加一句if (include_empty) ans 1;。8. 举一反三相关问题与变种思考理解这道题的精髓后我们可以看看它的一些变种这有助于深化对DP状态设计和去重技巧的理解。8.1 变种一计算所有本质不同的子序列不要求上升这是LeetCode上一道经典问题LeetCode 940. 不同的子序列 II。状态定义和转移非常相似但去重逻辑稍有不同。此时对于当前字符s[i]它可以接在所有之前出现过的字符后面没有上升约束。那么dp_i的初始值依然是1然后需要加上所有last[ch](ch 从 ‘a’ 到 ‘z’)。但是这样会导致重复计算吗会的。因为对于相同的字符我们仍然需要去重。解决方法和本题一样last[idx] dp_i。最终答案也是sum(last)。内层循环从遍历所有小于当前字符的字符变成了遍历所有26个字符。其核心思想依然是“每个字符结尾的总数只由该字符最后一次出现时的状态决定”。8.2 变种二计算所有上升子序列的数量允许重复如果去掉“本质不同”的要求只计算所有可能重复的上升子序列个数问题会简单很多。此时dp[i]表示以i结尾的上升子序列个数转移方程为dp[i] 1 sum(dp[j])for allj iands[j] s[i]。最终答案是所有dp[i]的和。这里不需要last数组因为重复是被允许的。8.3 变种三求最长的本质不同上升子序列的长度这结合了LIS和去重。我们可能需要一个DP数组dp[i]表示以i结尾的最长长度同时还需要一个last_len[26]记录以每个字符结尾的最长长度用于去重转移。但“最长”和“本质不同”结合时情况会更复杂因为一个更长的序列可能由多个较短的、结尾字符相同的序列转移而来去重时需要比较长度。这通常需要更复杂的状态设计。通过解决“本质上升序列”这道题我们掌握了一种处理子序列计数去重问题的强大范式以字符结尾进行状态聚合并通过维护每个字符的最后状态来避免重复计数。这个技巧在字符串DP中非常实用下次遇到类似问题时不妨先想想这个思路。