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时计算所有小于ch的字符prev对应的sum[prev]之和记为total。这个total就代表了在ch之前所有可以接上ch形成新序列的“基础序列”的数量。那么本次由ch产生的全新的本质不同上升子序列的数量就是total 1。这里的1就对应着序列ch本身。关键来了我们将这个新增的数量(total 1)加到dp[ch]上。注意是“加到”而不是“设为”。同时我们也要更新sum[ch]因为对于后续的字符来说当前这个ch以及以它结尾的所有序列都成为了“历史基础序列”。所以sum[ch]也需要增加相同的值(total 1)。但这里还有一个巨大的坑让我们用 “abac” 这个例子手动模拟一下这个看似正确的过程初始化dp[26] {0},sum[26] {0}。遇到 ‘a’ (索引0):total 小于 ‘a’ 的字符和为0。新增 011。dp[‘a’] 1- 变为1。sum[‘a’] 1- 变为1。遇到 ‘b’ (索引1):totalsum[‘a’] 1。新增 112。dp[‘b’] 2- 变为2。sum[‘b’] 2- 变为2。新增的2个序列是“b” 和 “ab”。遇到 ‘a’ (索引2):total 0小于 ‘a’ 的没有。新增 011。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]是0total_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时计算当前的total_new。计算delta total_new - last_total[ch]。如果last_total[ch]是-1第一次遇到那么delta就等于total_new 1不对因为last_total[ch] -1total_new - (-1) total_new 1。正好这样就把第一次遇到的1也统一到公式里了。更新dp[ch] delta。更新sum[ch] delta。更新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’ (i0):total_new0,last[‘a’]-1,delta 0 - (-1) 1。dp[‘a’]1,sum[‘a’]1,last[‘a’]0。‘b’ (i1):total_new sum[‘a’] 1,last[‘b’]-1,delta 1 - (-1) 2。dp[‘b’]2,sum[‘b’]2,last[‘b’]1。‘a’ (i2):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’ (i3):total_new sum[‘a’]sum[‘b’] 123,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 结尾的本质不同上升子序列个数 vectorlong long dp(CHAR_SET, 0); // sum[c] 表示在当前遍历位置之前以字符 c 结尾的序列总数用于计算前缀和 vectorlong long sum(CHAR_SET, 0); // lastTotal[c] 记录字符 c 上一次出现时小于 c 的字符的序列总和即当时的 total_new vectorlong 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; }代码关键点解析数据结构选择使用vectorlong long来存储dp,sum,lastTotal。long long是为了防止中间结果溢出即便取模在加法和乘法前也可能溢出int。字符集大小固定为26所以数组长度是常数。取模运算由于结果可能巨大题目通常要求对1e97取模。务必注意取模要在每一次加法、减法运算后进行而不是最后才取模否则中间过程可能已经溢出。减法后可能得到负数需要(a - b MOD) % MOD来保证结果非负。lastTotal数组的初始化与含义初始化为-1是一个技巧用于标识字符是否首次出现。在计算delta时我们通过判断lastTotal[idx] ! -1来区分两种情况。lastTotal[idx]严格记录的是上一次遇到该字符时计算出的total_new值。total_new的计算这里用了一个内层循环for (int i 0; i idx; i)来累加所有小于当前字符的sum[i]。这是算法中唯一的嵌套循环时间复杂度为 O(26 * n)对于长度 n200 的字符串是绰绰有余的。这也是整个算法 O(n) 复杂度的来源因为内层循环是常数26。delta的计算逻辑这是核心中的核心。代码中通过if-else清晰地区分了字符首次出现和非首次出现的情况对应了我们推导的两种公式。这种写法比用统一公式delta (total_new - lastTotal[idx] MOD) % MOD然后处理首次出现更清晰因为当lastTotal[idx] -1时统一公式会算出delta total_new 1但需要额外的逻辑来判断是否是第一次出现以决定是否补1不如这样直接判断来得直观。更新顺序先计算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)3317与算法输出一致。 对于 “aaa”只有字符 ‘a’所有子序列都是 “a”且来自不同位置但本质相同所以只有1个。 空串和单字符串是常见的边界条件算法应该能正确处理。4.2 复杂情况与去重验证让我们设计一个更复杂的例子 “abca”手动列举所有本质不同上升子序列长度为1: a, b, c长度为2: ab, ac, bc长度为3: abc总数为 331 7。算法运行过程简述处理 ‘a’: dp[a]1, sum[a]1, last[a]0。处理 ‘b’: total_newsum[a]1, dp[b]2, sum[b]2, last[b]1。处理 ‘c’: total_newsum[a]sum[b]123, dp[c]4, sum[c]4, last[c]3。处理 ‘a’: total_new0, last[a]0, delta0-00。dp[a]和sum[a]不变。最终结果 dp[a]dp[b]dp[c] 124 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 (1e97)总和小于 26 * 1e97 ≈ 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码|Σ|256O(256n) 对于 n200 也还是可以的51200次操作。但如果字符集是上万的全Unicode这个方法就太慢了。此时需要优化total_new的计算。我们计算total_new需要求sum[0] ... sum[idx-1]这是一个前缀和查询。我们可以用一个树状数组Fenwick Tree或线段树来维护sum数组。这样每次查询前缀和和更新单个值的操作都可以在 O(log|Σ|) 时间内完成。整体复杂度就降为 O(n log|Σ|)即使 |Σ| 很大也能高效处理。这是处理大字符集计数DP的常用技巧。5.3 如何输出具体的序列而不仅仅是计数这是一个更进阶的问题。我们的DP只记录了数量。如果要输出所有序列本质上需要回溯所有可能的状态转移路径这会导致指数级的输出对于长字符串不现实。但如果只是验证算法或者处理短字符串我们可以修改DP数组让它存储一个“序列列表”的集合如setstring但这样空间和时间开销都会变得非常大仅适用于教学和调试。在竞赛中通常只要求计数。5.4 本题与“不同的子序列”问题的联系与区别LeetCode上有一道经典题目“不同的子序列”Distinct Subsequences给定字符串S和T统计S中有多少个子序列等于T。那是一个双字符串的DP计数问题。而我们这道题可以看作是它的一个变种T不是一个给定的字符串而是所有可能的、满足上升性质的字符串的集合。我们的DP状态dp[c]类似于“不同的子序列”中匹配到T的某个位置时的计数。但“不同的子序列”问题通常不去重或者说子序列按位置区分而本题严格要求本质字符串内容去重因此状态定义和转移逻辑有根本不同。5.5 动态规划思想的本质再思考通过这道题我们可以深刻体会到动态规划的精髓定义状态和找到最优子结构。这里的“最优”在计数问题中就是“不重不漏地计数”。定义出“以字符结尾”的状态是这个题解法的灵魂。它抓住了“本质不同”这个约束的关键——重复只可能发生在相同的字符上。将状态与字符绑定而不是与位置绑定一下子就把去重这个复杂问题简化了。在平时练习时遇到计数类DP如果发现直接定义状态会导致重复计数不妨想想能不能换一个维度来定义状态比如从“位置”换到“值域”或者像本题一样换到“字符集”。这往往就是破题的关键。 动态规划去重技巧：从蓝桥杯真题解析本质不同上升子序列计数
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时计算所有小于ch的字符prev对应的sum[prev]之和记为total。这个total就代表了在ch之前所有可以接上ch形成新序列的“基础序列”的数量。那么本次由ch产生的全新的本质不同上升子序列的数量就是total 1。这里的1就对应着序列ch本身。关键来了我们将这个新增的数量(total 1)加到dp[ch]上。注意是“加到”而不是“设为”。同时我们也要更新sum[ch]因为对于后续的字符来说当前这个ch以及以它结尾的所有序列都成为了“历史基础序列”。所以sum[ch]也需要增加相同的值(total 1)。但这里还有一个巨大的坑让我们用 “abac” 这个例子手动模拟一下这个看似正确的过程初始化dp[26] {0},sum[26] {0}。遇到 ‘a’ (索引0):total 小于 ‘a’ 的字符和为0。新增 011。dp[‘a’] 1- 变为1。sum[‘a’] 1- 变为1。遇到 ‘b’ (索引1):totalsum[‘a’] 1。新增 112。dp[‘b’] 2- 变为2。sum[‘b’] 2- 变为2。新增的2个序列是“b” 和 “ab”。遇到 ‘a’ (索引2):total 0小于 ‘a’ 的没有。新增 011。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]是0total_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时计算当前的total_new。计算delta total_new - last_total[ch]。如果last_total[ch]是-1第一次遇到那么delta就等于total_new 1不对因为last_total[ch] -1total_new - (-1) total_new 1。正好这样就把第一次遇到的1也统一到公式里了。更新dp[ch] delta。更新sum[ch] delta。更新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’ (i0):total_new0,last[‘a’]-1,delta 0 - (-1) 1。dp[‘a’]1,sum[‘a’]1,last[‘a’]0。‘b’ (i1):total_new sum[‘a’] 1,last[‘b’]-1,delta 1 - (-1) 2。dp[‘b’]2,sum[‘b’]2,last[‘b’]1。‘a’ (i2):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’ (i3):total_new sum[‘a’]sum[‘b’] 123,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 结尾的本质不同上升子序列个数 vectorlong long dp(CHAR_SET, 0); // sum[c] 表示在当前遍历位置之前以字符 c 结尾的序列总数用于计算前缀和 vectorlong long sum(CHAR_SET, 0); // lastTotal[c] 记录字符 c 上一次出现时小于 c 的字符的序列总和即当时的 total_new vectorlong 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; }代码关键点解析数据结构选择使用vectorlong long来存储dp,sum,lastTotal。long long是为了防止中间结果溢出即便取模在加法和乘法前也可能溢出int。字符集大小固定为26所以数组长度是常数。取模运算由于结果可能巨大题目通常要求对1e97取模。务必注意取模要在每一次加法、减法运算后进行而不是最后才取模否则中间过程可能已经溢出。减法后可能得到负数需要(a - b MOD) % MOD来保证结果非负。lastTotal数组的初始化与含义初始化为-1是一个技巧用于标识字符是否首次出现。在计算delta时我们通过判断lastTotal[idx] ! -1来区分两种情况。lastTotal[idx]严格记录的是上一次遇到该字符时计算出的total_new值。total_new的计算这里用了一个内层循环for (int i 0; i idx; i)来累加所有小于当前字符的sum[i]。这是算法中唯一的嵌套循环时间复杂度为 O(26 * n)对于长度 n200 的字符串是绰绰有余的。这也是整个算法 O(n) 复杂度的来源因为内层循环是常数26。delta的计算逻辑这是核心中的核心。代码中通过if-else清晰地区分了字符首次出现和非首次出现的情况对应了我们推导的两种公式。这种写法比用统一公式delta (total_new - lastTotal[idx] MOD) % MOD然后处理首次出现更清晰因为当lastTotal[idx] -1时统一公式会算出delta total_new 1但需要额外的逻辑来判断是否是第一次出现以决定是否补1不如这样直接判断来得直观。更新顺序先计算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)3317与算法输出一致。 对于 “aaa”只有字符 ‘a’所有子序列都是 “a”且来自不同位置但本质相同所以只有1个。 空串和单字符串是常见的边界条件算法应该能正确处理。4.2 复杂情况与去重验证让我们设计一个更复杂的例子 “abca”手动列举所有本质不同上升子序列长度为1: a, b, c长度为2: ab, ac, bc长度为3: abc总数为 331 7。算法运行过程简述处理 ‘a’: dp[a]1, sum[a]1, last[a]0。处理 ‘b’: total_newsum[a]1, dp[b]2, sum[b]2, last[b]1。处理 ‘c’: total_newsum[a]sum[b]123, dp[c]4, sum[c]4, last[c]3。处理 ‘a’: total_new0, last[a]0, delta0-00。dp[a]和sum[a]不变。最终结果 dp[a]dp[b]dp[c] 124 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 (1e97)总和小于 26 * 1e97 ≈ 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码|Σ|256O(256n) 对于 n200 也还是可以的51200次操作。但如果字符集是上万的全Unicode这个方法就太慢了。此时需要优化total_new的计算。我们计算total_new需要求sum[0] ... sum[idx-1]这是一个前缀和查询。我们可以用一个树状数组Fenwick Tree或线段树来维护sum数组。这样每次查询前缀和和更新单个值的操作都可以在 O(log|Σ|) 时间内完成。整体复杂度就降为 O(n log|Σ|)即使 |Σ| 很大也能高效处理。这是处理大字符集计数DP的常用技巧。5.3 如何输出具体的序列而不仅仅是计数这是一个更进阶的问题。我们的DP只记录了数量。如果要输出所有序列本质上需要回溯所有可能的状态转移路径这会导致指数级的输出对于长字符串不现实。但如果只是验证算法或者处理短字符串我们可以修改DP数组让它存储一个“序列列表”的集合如setstring但这样空间和时间开销都会变得非常大仅适用于教学和调试。在竞赛中通常只要求计数。5.4 本题与“不同的子序列”问题的联系与区别LeetCode上有一道经典题目“不同的子序列”Distinct Subsequences给定字符串S和T统计S中有多少个子序列等于T。那是一个双字符串的DP计数问题。而我们这道题可以看作是它的一个变种T不是一个给定的字符串而是所有可能的、满足上升性质的字符串的集合。我们的DP状态dp[c]类似于“不同的子序列”中匹配到T的某个位置时的计数。但“不同的子序列”问题通常不去重或者说子序列按位置区分而本题严格要求本质字符串内容去重因此状态定义和转移逻辑有根本不同。5.5 动态规划思想的本质再思考通过这道题我们可以深刻体会到动态规划的精髓定义状态和找到最优子结构。这里的“最优”在计数问题中就是“不重不漏地计数”。定义出“以字符结尾”的状态是这个题解法的灵魂。它抓住了“本质不同”这个约束的关键——重复只可能发生在相同的字符上。将状态与字符绑定而不是与位置绑定一下子就把去重这个复杂问题简化了。在平时练习时遇到计数类DP如果发现直接定义状态会导致重复计数不妨想想能不能换一个维度来定义状态比如从“位置”换到“值域”或者像本题一样换到“字符集”。这往往就是破题的关键。