动态规划解本质不同上升子序列计数：从LIS到状态转移优化-编程实验室

1. 问题引入：从“上升序列”到“本质不同”

最近在复盘蓝桥杯国赛的真题，翻到了2020年第十一届C/C++大学A组的这道“本质上升序列”。题目本身描述很简洁：给定一个字符串，要求计算其所有“本质不同”的“上升子序列”的个数。很多同学第一眼看到“上升子序列”，会立刻联想到经典的“最长上升子序列”（LIS）动态规划问题，但仔细一看，这里的“上升”指的是字符串中字符的字典序递增，而“本质不同”则意味着即使子序列内容相同，只要在原字符串中的位置（下标）不同，就算作不同的序列。这和我们平时处理子序列问题的思路有很大不同，不是求最长，而是求所有不重复的、满足特定条件的子序列的数量。这种计数类动态规划问题，在算法竞赛中非常考验对状态定义和转移方程的理解深度，稍有不慎就会重复计数或者漏算。

我记得当时第一次看到这题，心里咯噔一下，因为常规的LIS动态规划数组dp[i]通常表示以第i个元素结尾的最长上升子序列长度，转移时关注的是长度最大值。但这里要求的是数量，并且是“本质不同”的数量，直接套用模板肯定不行。我们需要设计一个新的状态，来精确记录以某个字符结尾的、满足条件的所有不同子序列的数量，同时还要避免因为同一个子序列可以通过不同路径形成而导致的重复计算。这其中的状态定义、转移逻辑和去重技巧，正是这道题的核心价值所在，也是动态规划思想从“最值问题”向“计数问题”拓展的一个典型范例。理解清楚这道题，对于处理更复杂的序列计数问题，比如带限制条件的子序列个数、不同子序列个数等，都会有很大帮助。

2. 核心概念拆解：什么是“本质上升序列”？

在动手写代码之前，我们必须把题目中的两个关键约束条件——“上升”和“本质不同”——彻底搞清楚。这直接决定了我们动态规划状态的定义。

2.1 “上升”的字典序定义

在这个问题里，“上升”不是指数值大小，而是指字符在字典序（通常是ASCII码顺序）上的严格递增。例如，在字符串"abc"中，子序列"a","b","c","ab","ac","bc","abc"都是上升的，因为后一个字符的ASCII码大于前一个。而"ba"就不是，因为'b'>'a'不满足从前往后递增。这里有一个关键点：空序列通常不计入（除非题目特别说明），我们一般从长度为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动态规划解法。对于数组arr，dp_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"来模拟一下。

按照上述公式：

i=0(s[0]='a'):dp[0] = 1(只有"a")
i=1(s[1]='b'):j可以取0，因为'a' < 'b'。dp[1] = dp[0] + 1 = 1 + 1 = 2。这2个序列是："b"和"ab"。正确。
i=2(s[2]='a'): 找j < 2且s[j] < 'a'。没有字符比'a'小（ASCII码），所以dp[2] = 1(只有"a"，这里指第二个'a')。正确。
i=3(s[3]='b'): 找j < 3且s[j] < 'b'，即'a'。j可以是0和2。
- 从j=0转移过来：意味着在所有以s[0](第一个'a') 结尾的序列后面加上s[3]('b')。以s[0]结尾的序列有："a"。得到新序列"ab"。
- 从j=2转移过来：意味着在所有以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(); vector<long 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"，运行过程如下：

i=0: dp[0]=1
i=1: j=0, s 0 < s 1 -> dp[1] += dp[0] => dp[1] = 1+1=2
i=2: j=0, s 0 不小于 s 2 ；j=1, s 1 > s 2 。无转移，dp[2]=1
i=3: j=0, s 0 < s 3 -> dp[3] += dp[0] => dp[3]=1+1=2； j=1, 不满足； j=2, s 2 < s 3 -> dp[3] += dp[2] => dp[3]=2+1=3。
ans = dp[0]+dp[1]+dp[2]+dp[3] = 1+2+1+3 = 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'不行（b=b）。所以没有长度为3的合法序列。总数为4+3=7，与程序结果一致。

4.4 一个关键的优化点：去重？不，是理解！

网上有些关于这道题的讨论，会提到“去重”的问题。他们指的是另一种重复：当字符串中存在相同字符时，直接累加dp[j]可能会导致以相同字符结尾的子序列被重复转移。

考虑字符串"abb"：

i=0: dp[0]=1 ("a")
i=1: j=0, s 0 <s 1 -> dp[1] = 1 + dp[0] = 2 ("b","ab")
i=2: j=0, s 0 <s 2 -> dp[2] += dp[0] => dp[2]=1+1=2； j=1, s 1 不小于 s 2 。所以 dp[2]=2。最终 ans = 1+2+2=5。枚举验证："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万次运算）通常是可接受的。但如果我们追求更优的解法，或者应对更大的数据范围（比如 n=10^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]表示到目前为止，所有以字符 ('a'+k) 结尾的合法子序列的总数。

算法流程可以优化为 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(); vector<long 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 long（64位整数）。即便如此，也可能溢出。蓝桥杯的题目有时会要求将结果对某个大数（如1e9+7）取模。这时，我们在每一步加法运算后都应及时取模，避免中间结果溢出。

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]来转移。对于字符集有限的情况，利用前缀和思想可以大幅优化。掌握这个模型，就能应对许多变种的子序列计数问题。在竞赛中，清晰的思路和对“本质不同”的准确把握，是快速解出此类题目的关键。