动态规划去重技巧：从蓝桥杯真题解析本质不同上升子序列计数

1. 项目概述：从一道国赛真题看动态规划的本质

“本质上升序列”这道题，是2020年蓝桥杯国赛C++ B组的一道经典题目。乍一看题目，很多同学可能会觉得这不就是个简单的序列统计问题吗？但真正上手去解，才会发现里面藏着动态规划（DP）思想最精妙、也最考验基本功的部分。它不像背包问题那样有明确的模板，也不像图论DP那样有固定的状态转移方程，它要求你从最朴素的“上升”定义出发，自己构建状态，并小心翼翼地处理“本质不同”这个关键约束。我当年带学生备战国赛时，这道题是必讲的压轴题之一，因为它完美地诠释了如何将实际问题抽象为DP模型，以及如何处理去重这个DP中的老大难问题。今天，我们就来彻底拆解这道题，不仅告诉你答案怎么算，更要讲清楚每一步背后的“为什么”，让你下次遇到类似的字符串计数、序列DP问题时，能一眼看穿本质。

这道题的核心是：给定一个字符串（由小写字母组成），请你统计其中所有“本质不同的上升子序列”的个数。这里有两个关键点：“上升”意味着子序列中每个字符都比前一个字符大（按字母序）；“本质不同”意味着即使子序列在字符串中的位置（下标）不同，但只要组成的字符串相同，就算作同一个。例如字符串 “abc”，它的上升子序列有 “a”, “b”, “c”, “ab”, “ac”, “bc”, “abc”，这些都是本质不同的。但如果字符串是 “aba”，子序列 “a”（取第一个字符）和 “a”（取第三个字符）虽然来自不同位置，但序列都是 “a”，所以只算一个。题目最终要对一个超长字符串（比如长度达到200）进行统计，结果可能非常大，通常要求取模。这直接排除了暴力枚举所有子序列（2^n复杂度）的可能性，必须用动态规划在O(n^2)甚至更优的复杂度内解决。

2. 核心思路拆解：如何定义“状态”与处理“去重”

面对这种计数类DP问题，第一步也是最难的一步，就是定义出正确的DP状态。状态定义错了，后面全盘皆输。

2.1 状态定义的常见陷阱与正确思路

最直观的想法可能是定义dp[i]为以第i个字符结尾的本质不同上升子序列的个数。这个想法很自然，类似于最长上升子序列（LIS）问题的思路。但这样定义马上会遇到一个致命问题：重复计数。

举个例子，字符串 “abac”。我们考虑以最后一个字符 ‘c’ 结尾的上升子序列。按照dp[i]的思路，我们需要找到所有在i之前、且字符小于 ‘c’ 的位置j，然后把dp[j]都加起来。对于 ‘c’ 来说，前面的 ‘a’, ‘b’, ‘a’ 都小于它。但这里有两个 ‘a’，以第一个 ‘a’ 结尾的序列集合和以第三个 ‘a’ 结尾的序列集合，它们很可能包含大量相同的序列（比如单独的 “a”）。如果简单累加dp[0] + dp[1] + dp[2]，就会导致这些由 ‘a’ 产生的相同序列被重复计算。

问题的根源在于，我们的状态dp[i]绑定的是“位置”，而题目要求的是“字符序列”本质不同。当相同字符出现在不同位置时，它们产生的许多子序列是重复的。因此，我们必须把状态从“以某个位置结尾”转变到“以某个字符结尾”。

正确的状态定义：dp[c]表示以字符c结尾的本质不同上升子序列的个数。这里c是字符本身（比如 ‘a’ 到 ‘z’），而不是下标。这样一来，无论字符 ‘a’ 在字符串中出现多少次，所有以 ‘a’ 结尾的序列都归到dp[‘a’]这个状态里，从根源上避免了因位置不同导致的重复。

注意：这个转变是理解本题的关键。DP的状态不一定非要和数组下标绑定，它可以和问题的某个“维度”绑定，在这里就是字符集。这大大降低了状态数量（只有26个），也简化了去重逻辑。

2.2 状态转移方程的推导

状态定义好了，接下来看怎么转移。假设我们正在遍历字符串，当前遍历到的字符是s[i] = ch。我们需要更新以ch结尾的序列数量dp[ch]。

一个新的以ch结尾的上升子序列是怎么来的？它必然是在某个以比ch小的字符prev结尾的子序列后面，追加一个ch构成的。所以，dp[ch]应该增加所有dp[prev]的和，其中prev是小于ch的所有字符。

但这就够了吗？不够。我们还漏掉了一类非常重要的序列：单独一个ch字符本身也是一个合法的、长度为1的上升子序列。所以，在每次遇到字符ch时，除了加上前面小字符的序列数，还必须为ch本身这个序列计数加1。

然而，直接加1又会引入新的重复问题。考虑字符串 “aa”。当处理第一个 ‘a’ 时，dp[‘a’]从0变为1（增加了序列 “a”）。当处理第二个 ‘a’ 时，如果我们再次给dp[‘a’]加1，就又计入了一个 “a” 序列，这就重复了。因为这两个 “a” 虽然是不同位置的字符，但形成的序列 “a” 是同一个。

所以，我们不能在每次遇到字符时都无条件给dp[ch]加1。正确的做法是：确保每个“本质不同的序列”只在它第一次被构造出来时被计数。对于单个字符序列，它应该在字符第一次出现时被计入。但我们的状态dp[ch]是累积的，包含了历史信息。我们需要一个方法来区分“新增”的序列和从之前转移过来的序列。

这里的一个巧妙方法是：在遍历过程中，动态地、增量式地更新dp数组。我们维护一个sum数组，sum[c]表示在当前遍历位置之前，以字符c结尾的序列总数。当我们遇到一个新的字符ch时：

1. 计算所有小于ch的字符prev对应的sum[prev]之和，记为total。这个total就代表了在ch之前，所有可以接上ch形成新序列的“基础序列”的数量。
2. 那么，本次由ch产生的全新的本质不同上升子序列的数量就是total + 1。这里的+1就对应着序列ch本身。
3. 关键来了：我们将这个新增的数量(total + 1)，加到dp[ch]上。注意，是“加到”而不是“设为”。同时，我们也要更新sum[ch]，因为对于后续的字符来说，当前这个ch以及以它结尾的所有序列，都成为了“历史基础序列”。所以sum[ch]也需要增加相同的值(total + 1)。

但这里还有一个巨大的坑！让我们用 “abac” 这个例子，手动模拟一下这个看似正确的过程：

• 初始化dp[26] = {0},sum[26] = {0}。
• 遇到 ‘a’ (索引0):total= 小于 ‘a’ 的字符和为0。新增 = 0+1=1。dp[‘a’] += 1-> 变为1。sum[‘a’] += 1-> 变为1。
• 遇到 ‘b’ (索引1):total=sum[‘a’]= 1。新增 = 1+1=2。dp[‘b’] += 2-> 变为2。sum[‘b’] += 2-> 变为2。
  • 新增的2个序列是：“b” 和 “ab”。
• 遇到 ‘a’ (索引2):total= 0（小于 ‘a’ 的没有）。新增 = 0+1=1。dp[‘a’] += 1-> 变为2。sum[‘a’] += 1-> 变为2。
  • 等等，这里出问题了！我们又给dp[‘a’]加了一个1，这意味着我们又计入了一个 “a” 序列。但第二个 ‘a’ 产生的序列 “a”，和第一个 ‘a’ 产生的序列 “a” 是本质相同的！我们重复计数了。

问题出在哪里？出在当我们第二次遇到 ‘a’ 时，我们仍然用total + 1来计算新增，这个+1就代表了新的、单独的 “a”。但事实上，这个单独的 “a” 在第一次遇到 ‘a’ 时已经被计入dp[‘a’]了。所以，对于非首次出现的字符，我们不能再次给它加这个单独的 “1”。

那么，如何知道是不是首次出现呢？我们需要记录每个字符上一次被处理时，它所“带来”的新增序列数。更准确地说，当我们在位置i遇到字符ch时，我们需要知道，在上一次遇到ch时，我们基于当时的total_old计算出的新增序列数add_old = total_old + 1。这个add_old已经全部被计入dp[ch]和sum[ch]了。

现在，在当前位置，我们计算出了新的total_new（基于当前的sum数组，它包含了截止到当前位置之前的所有历史信息）。那么，本次真正新增的、以ch结尾的本质不同序列数是多少？是total_new + 1吗？不是，因为total_new里可能包含了从上一次ch出现到这一次ch出现之间，新产生的一些可以接在ch前面的序列。但同时，total_new也包含了total_old那一部分。而由total_old产生的那些序列，在上一次遇到ch时，已经和当时的ch组合过了，那些组合序列（即add_old中除了单独的’ch’之外的部分）已经被计入dp[ch]了。

所以，本次真正全新的组合，是基于(total_new - total_old)这部分新出现的基础序列。它们和当前的ch组合，产生(total_new - total_old)个新序列。除此之外，还有单独的 “ch” 这个序列吗？没有，因为它早已被计入。

因此，对于重复出现的字符ch，本次新增的序列数add_new = total_new - total_old。

而对于第一次出现的字符，total_old不存在，我们可以认为total_old = 0，并且需要计入单独的 “ch”，所以add_new = total_new + 1。这个公式和上面推导的add_new = total_new - total_old在total_old = 0时是不一致的，因为差了1。为了统一，我们可以这样处理：记录每个字符上一次遇到时的total值，记为last_total[ch]。初始化last_total[ch] = 0。那么：

• 当第一次遇到ch时，last_total[ch]是0，total_new是当前算出的值。按照我们的分析，应该新增total_new + 1。这等价于total_new - last_total[ch] + 1。
• 当非第一次遇到ch时，last_total[ch]是上一次的total值，应该新增total_new - last_total[ch]。

发现规律了吗？我们可以用一个统一的公式：add_new = total_new - last_total[ch]。然后，如果是第一次遇到该字符，我们再额外地、单独地补加一个1。但是，补加这个1的操作，一生只能做一次，否则就会重复添加单个字符序列。

更优雅的实现方式是：在初始化时，我们将last_total[ch]设置为一个无效值（比如-1），表示从未遇到过。当遇到字符ch时：

1. 计算当前的total_new。
2. 计算delta = total_new - last_total[ch]。如果last_total[ch]是-1（第一次遇到），那么delta就等于total_new + 1？不对，因为last_total[ch] = -1，total_new - (-1) = total_new + 1。正好！这样就把第一次遇到的+1也统一到公式里了。
3. 更新dp[ch] += delta。
4. 更新sum[ch] += delta。
5. 更新last_total[ch] = total_new。注意，这里更新为total_new，而不是total_new + 1或其他。因为last_total[ch]记录的是“上一次遇到ch时，小于ch的字符的序列总和”，这个值就是total_new。

这个方法是正确的。让我们最后用 “abac” 验证一下：

• 初始化dp[26]={0},sum[26]={0},last[26]={-1}。
• ‘a’ (i=0):total_new=0,last[‘a’]=-1,delta = 0 - (-1) = 1。dp[‘a’]=1,sum[‘a’]=1,last[‘a’]=0。
• ‘b’ (i=1):total_new = sum[‘a’] = 1,last[‘b’]=-1,delta = 1 - (-1) = 2。dp[‘b’]=2,sum[‘b’]=2,last[‘b’]=1。
• ‘a’ (i=2):total_new = 0(小于’a’的没有)，last[‘a’]=0(上次遇到’a’时的total)，delta = 0 - 0 = 0。dp[‘a’]不变，sum[‘a’]不变，last[‘a’]=0。
  • 完美！第二次遇到’a’时，delta为0，没有新增任何序列。因为小于’a’的序列和没变（还是0），而单独的’a’序列早已被计入。
• ‘c’ (i=3):total_new = sum[‘a’]+sum[‘b’] = 1+2=3,last[‘c’]=-1,delta = 3 - (-1) = 4。dp[‘c’]=4,sum[‘c’]=4,last[‘c’]=3。
  • 新增的4个序列是：“c”, “ac”, “bc”, “abc”。（注意：“aac”不是上升序列，“abac”也不是，因为’a’之后又出现了’a’和’c’，但序列中’a’重复了？不，子序列“aac”中，下标2的’a’不大于下标0的’a’，违反上升规则。所以我们的算法不会产生它。）

最终，所有本质不同上升子序列的总数，就是dp[‘a’] + dp[‘b’] + … + dp[‘z’]。对于 “abac”，总数是dp[‘a’]=1, dp[‘b’]=2, dp[‘c’]=4，总和为7。与我们之前手动列举的 “a”, “b”, “c”, “ab”, “ac”, “bc”, “abc” 这7个序列相符。

实操心得：这个last_total数组是去重的核心。它记录了每个字符“上一次”的状态，确保了我们只添加新的、不重复的转移。这是解决“本质不同”计数问题的关键技巧，在很多字符串去重DP中都有应用。务必理解delta = total_new - last_total[ch]这个式子的物理意义：它代表了自从字符ch上次出现以来，新产生的、可以接在ch前面的基础序列数量。这部分基础序列与当前的ch组合，产生的就是全新的、不重复的上升序列。

3. 算法实现与代码逐行解析

理解了上面的推导过程，代码实现就相对清晰了。我们采用C++来实现，并会处理大数取模的问题（因为结果可能非常大）。下面给出完整的代码，并附上逐行解析。

#include <iostream> #include <string> #include <vector> using namespace std; const int MOD = 1000000007; // 常见的大质数模数 const int CHAR_SET = 26; // 小写字母集 int countDistinctIncreasingSubsequences(const string& s) { // dp[c] 表示以字符 c 结尾的本质不同上升子序列个数 vector<long long> dp(CHAR_SET, 0); // sum[c] 表示在当前遍历位置之前，以字符 c 结尾的序列总数（用于计算前缀和） vector<long long> sum(CHAR_SET, 0); // lastTotal[c] 记录字符 c 上一次出现时，小于 c 的字符的序列总和（即当时的 total_new） vector<long long> lastTotal(CHAR_SET, -1); // 初始化为 -1，表示未出现过 for (char ch : s) { int idx = ch - 'a'; // 将字符映射到 0-25 的索引 // 1. 计算 total_new：所有小于当前字符 ch 的字符的序列总和 long long total_new = 0; for (int i = 0; i < idx; ++i) { total_new = (total_new + sum[i]) % MOD; } // 2. 计算本次新增的序列数 delta // 公式：delta = total_new - lastTotal[idx] // 由于 lastTotal 初始为 -1，利用取模运算处理负数 long long delta = total_new; if (lastTotal[idx] != -1) { delta = (delta - lastTotal[idx] + MOD) % MOD; // 非首次出现，直接减 } else { // 首次出现，delta = total_new - (-1) = total_new + 1 delta = (delta + 1) % MOD; } // 3. 更新 dp 和 sum 数组 dp[idx] = (dp[idx] + delta) % MOD; sum[idx] = (sum[idx] + delta) % MOD; // 4. 更新 lastTotal 为当前的 total_new lastTotal[idx] = total_new; } // 5. 统计结果：所有以不同字符结尾的序列数之和 long long ans = 0; for (int i = 0; i < CHAR_SET; ++i) { ans = (ans + dp[i]) % MOD; } return ans; } int main() { // 题目示例字符串，实际比赛时可能是从文件或标准输入读取长字符串 string s = "abac"; cout << countDistinctIncreasingSubsequences(s) << endl; // 输出应为 7 return 0; }

代码关键点解析：

1. 数据结构选择：使用vector<long long>来存储dp,sum,lastTotal。long long是为了防止中间结果溢出，即便取模，在加法和乘法前也可能溢出int。字符集大小固定为26，所以数组长度是常数。
2. 取模运算：由于结果可能巨大，题目通常要求对1e9+7取模。务必注意：取模要在每一次加法、减法运算后进行，而不是最后才取模，否则中间过程可能已经溢出。减法后可能得到负数，需要(a - b + MOD) % MOD来保证结果非负。
3. lastTotal数组的初始化与含义：初始化为-1是一个技巧，用于标识字符是否首次出现。在计算delta时，我们通过判断lastTotal[idx] != -1来区分两种情况。lastTotal[idx]严格记录的是上一次遇到该字符时，计算出的total_new值。
4. total_new的计算：这里用了一个内层循环for (int i = 0; i < idx; ++i)来累加所有小于当前字符的sum[i]。这是算法中唯一的嵌套循环，时间复杂度为 O(26 * n)，对于长度 n=200 的字符串是绰绰有余的。这也是整个算法 O(n) 复杂度的来源（因为内层循环是常数26）。
5. delta的计算逻辑：这是核心中的核心。代码中通过if-else清晰地区分了字符首次出现和非首次出现的情况，对应了我们推导的两种公式。这种写法比用统一公式delta = (total_new - lastTotal[idx] + MOD) % MOD然后处理首次出现更清晰，因为当lastTotal[idx] = -1时，统一公式会算出delta = total_new + 1，但需要额外的逻辑来判断是否是第一次出现以决定是否补1，不如这样直接判断来得直观。
6. 更新顺序：先计算delta，然后用它同时更新dp和sum。最后更新lastTotal。这个顺序不能乱，因为lastTotal记录的是本次更新前的状态。

复杂度分析：

• 时间复杂度：O(26 * n)，其中 n 是字符串长度。内层循环固定26次，因此是线性复杂度。
• 空间复杂度：O(1)，只使用了固定大小的几个数组（26长度）。

4. 算法正确性验证与边界测试

理论推导和代码都有了，我们还需要用更多的测试用例来验证算法的正确性，并考虑边界情况。

4.1 基础测试用例

我们写一个简单的测试函数来跑几个例子：

void test() { cout << "Test 1 (abac): " << countDistinctIncreasingSubsequences("abac") << endl; // 预期 7 cout << "Test 2 (abc): " << countDistinctIncreasingSubsequences("abc") << endl; // 预期 7 cout << "Test 3 (aaa): " << countDistinctIncreasingSubsequences("aaa") << endl; // 预期 1 (只有 "a") cout << "Test 4 (空串): " << countDistinctIncreasingSubsequences("") << endl; // 预期 0 cout << "Test 5 (a): " << countDistinctIncreasingSubsequences("a") << endl; // 预期 1 cout << "Test 6 (zabc): " << countDistinctIncreasingSubsequences("zabc") << endl; // 手动计算验证 }

对于 “abc”，所有子序列都是上升的，且本质不同。子序列个数为：C(3,1)+C(3,2)+C(3,3)=3+3+1=7，与算法输出一致。 对于 “aaa”，只有字符 ‘a’，所有子序列都是 “a”，且来自不同位置，但本质相同，所以只有1个。 空串和单字符串是常见的边界条件，算法应该能正确处理。

4.2 复杂情况与去重验证

让我们设计一个更复杂的例子 “abca”：

• 手动列举所有本质不同上升子序列：
  • 长度为1: a, b, c
  • 长度为2: ab, ac, bc
  • 长度为3: abc
  • 总数为 3+3+1 = 7。
• 算法运行过程简述：
  • 处理 ‘a’: dp[a]=1, sum[a]=1, last[a]=0。
  • 处理 ‘b’: total_new=sum[a]=1, dp[b]=2, sum[b]=2, last[b]=1。
  • 处理 ‘c’: total_new=sum[a]+sum[b]=1+2=3, dp[c]=4, sum[c]=4, last[c]=3。
  • 处理 ‘a’: total_new=0, last[a]=0, delta=0-0=0。dp[a]和sum[a]不变。
  • 最终结果 dp[a]+dp[b]+dp[c] = 1+2+4 = 7。正确。

这个例子验证了当字符重复出现，且后面没有更小的字符可以形成新序列时，delta为0，不会产生重复计数。

4.3 大数取模与溢出测试

对于超长字符串，结果可能远超long long范围，必须依赖取模。我们需要确保取模运算的正确性。可以构造一个全 ‘a’ 到 ‘z’ 循环的长字符串，用一个小模数（比如10007）测试，同时用Python等支持大数的语言写一个暴力搜索（对于短字符串）或相同逻辑的脚本进行对拍，确保结果一致。

一个常见的取模陷阱：在计算total_new的累加时，total_new = (total_new + sum[i]) % MOD;这个写法是正确的。但如果sum[i]已经取过模，而total_new在累加过程中可能超过long long范围吗？不会，因为最多累加26次，每次值都小于MOD (1e9+7)，总和小于 26 * 1e9+7 ≈ 2.6e10，这在long long(约9e18) 的范围内是安全的。但为了绝对安全和养成好习惯，每次都取模是推荐的。

5. 常见问题与思维拓展

5.1 为什么不能直接用“以位置结尾”的DP？

这是初学者最容易掉进的坑。我们再来深入对比一下。 假设定义dp[i]为以s[i]结尾的本质不同上升子序列数。状态转移：dp[i] = 1 + sum(dp[j])，其中j < i且s[j] < s[i]，并且需要对j去重——如果存在j1和j2使得s[j1] == s[j2]，那么dp[j1]和dp[j2]贡献的序列集合会有大量重复（所有以该字符结尾的相同序列）。去重极其困难，需要在转移时比较序列集合，复杂度无法承受。 而“以字符结尾”的DP，天然地将所有相同字符结尾的序列归并到一个状态里，去重就在状态定义层面完成了。这是一种“状态压缩”的思想，将“位置”维度压缩到了“字符”维度。

5.2 如果字符集很大（比如是整个ASCII码或Unicode）怎么办？

我们的算法时间复杂度是 O(|Σ| * n)，其中 |Σ| 是字符集大小。对于小写字母，|Σ|=26，效率很高。如果字符集很大，比如是0-255的ASCII码，|Σ|=256，O(256n) 对于 n=200 也还是可以的（51200次操作）。但如果字符集是上万的全Unicode，这个方法就太慢了。

此时需要优化total_new的计算。我们计算total_new需要求sum[0] + ... + sum[idx-1]，这是一个前缀和查询。我们可以用一个树状数组（Fenwick Tree）或线段树来维护sum数组。这样，每次查询前缀和和更新单个值的操作都可以在 O(log|Σ|) 时间内完成。整体复杂度就降为 O(n log|Σ|)，即使 |Σ| 很大也能高效处理。这是处理大字符集计数DP的常用技巧。

5.3 如何输出具体的序列，而不仅仅是计数？

这是一个更进阶的问题。我们的DP只记录了数量。如果要输出所有序列，本质上需要回溯所有可能的状态转移路径，这会导致指数级的输出，对于长字符串不现实。但如果只是验证算法，或者处理短字符串，我们可以修改DP数组，让它存储一个“序列列表”的集合（如set<string>），但这样空间和时间开销都会变得非常大，仅适用于教学和调试。在竞赛中，通常只要求计数。

5.4 本题与“不同的子序列”问题的联系与区别

LeetCode上有一道经典题目“不同的子序列”（Distinct Subsequences），给定字符串S和T，统计S中有多少个子序列等于T。那是一个双字符串的DP计数问题。而我们这道题可以看作是它的一个变种：T不是一个给定的字符串，而是所有可能的、满足上升性质的字符串的集合。我们的DP状态dp[c]类似于“不同的子序列”中，匹配到T的某个位置时的计数。但“不同的子序列”问题通常不去重（或者说，子序列按位置区分），而本题严格要求本质（字符串内容）去重，因此状态定义和转移逻辑有根本不同。

5.5 动态规划思想的本质再思考

通过这道题，我们可以深刻体会到动态规划的精髓：定义状态和找到最优子结构。这里的“最优”在计数问题中就是“不重不漏地计数”。定义出“以字符结尾”的状态，是这个题解法的灵魂。它抓住了“本质不同”这个约束的关键——重复只可能发生在相同的字符上。将状态与字符绑定，而不是与位置绑定，一下子就把去重这个复杂问题简化了。

在平时练习时，遇到计数类DP，如果发现直接定义状态会导致重复计数，不妨想想能不能换一个维度来定义状态，比如从“位置”换到“值域”，或者像本题一样换到“字符集”。这往往就是破题的关键。