1. 问题引入从“上升”到“本质上升”的跨越如果你刷过一些算法题或者参加过像蓝桥杯这样的编程竞赛对“最长上升子序列”Longest Increasing Subsequence, LIS这个概念一定不陌生。经典的动态规划解法dp[i]表示以第i个元素结尾的最长上升子序列长度状态转移方程是dp[i] max(dp[j]) 1其中j i且nums[j] nums[i]。这个模型是理解序列问题动态规划思想的绝佳入门。但2020年蓝桥杯国赛Python组的一道题把这个问题推向了另一个维度。题目叫“本质上升序列”。初看名字你可能觉得只是LIS的一个变种无非是求长度或者数量。但当你真正读题尤其是看到那个长达200个字符的字符串时才会意识到它想考的远不止于此。它考的不仅仅是“上升”更是“本质不同”。这就像你学会了数数现在要求你数清楚一个巨大迷宫里所有不重复的路径有多少条而且每条路径还必须满足严格的上升规则。这道题当年卡住了不少人。不是因为动态规划本身有多难而是“本质不同”这个约束让状态的定义和转移变得异常棘手。直接套用经典LIS模型去计数会重复计算大量相同的子序列。比如字符串 “abc”子序列 “ac” 可以由选取第一个和第三个字符得到但“本质”上它只是一个序列。如何让动态规划的状态能够识别并合并这些“本质相同”的路径就是这道题的核心难点。这也是为什么它出现在国赛它考察的是对动态规划状态设计的深刻理解以及将复杂约束转化为可计算模型的能力。接下来我将带你彻底拆解这道题。我们会从最暴力的思路开始看看为什么它行不通然后一步步推导出正确的动态规划状态定义并给出两种不同思维角度的解法。最后我会分享一些在竞赛中处理此类“去重计数”问题的通用思路。2. 题目解析与暴力思路的陷阱首先我们必须明确题目的具体要求。题目给定一个字符串2020年真题给的是一个小写字母字符串长度可达200要求我们计算其所有“本质不同的上升子序列”的个数并对结果取模通常是10^9 7。这里需要精确定义两个关键概念上升子序列从原字符串中按顺序取出若干个字符可以不连续构成一个新的序列。这个新序列中每个字符的ASCII码值必须严格大于前一个字符的ASCII码值。这就是“上升”的含义它比普通的“非降序”更严格。本质不同只要子序列的内容即构成的字符串不同就算作不同的子序列。即使它们来自原字符串中不同的位置组合只要最终拼出来的字符串一样就视为同一个。举个例子字符串abac。有效的上升子序列有”a”,”b”,”c”,”ab”,”ac”,”bc”,”abc”。注意”aa”不是因为’a’不大于’a’”ba”也不是因为顺序不对。那么本质不同的有哪些呢”a”这个子序列你可以从第一个位置取也可以从第三个位置取。但无论从哪里取得到的都是字符串”a”。所以在“本质不同”的计数里”a”只算1个而不是2个。最直观的暴力方法是深度优先搜索DFS遍历字符串的每个位置决定“选”或“不选”当前字符如果选则需要保证它大于已选序列的最后一个字符。最后将得到的所有序列放入一个集合Set中去重集合的大小就是答案。这个思路清晰易懂但为什么是陷阱呢因为时间复杂度是指数级的。对于一个长度为n的字符串每个字符有选或不选两种可能最坏情况下会生成2^n个子序列。当n200时2^200是一个天文数字任何计算机都无法在有限时间内完成。因此暴力搜索在实际竞赛中毫无用处我们必须寻找多项式时间的解法而动态规划正是为此而生。然而将经典LIS的计数方法直接拿过来用我们会遇到重复计数的问题。经典LIS计数的一种思路是dp[i]表示以第i个字符结尾的上升子序列的个数。那么dp[i]就等于所有j i且s[j] s[i]的dp[j]之和再加上1表示单独以s[i]作为一个序列。但这样计算对于”abac”中的’a’第一个’a’和第三个’a’都会被计算一次dp1它们自身。在后续计算以’c’结尾的序列时我们会累加所有结尾小于’c’的dp值这就会把两个’a’产生的序列”ac”各算一次导致重复。问题的根源在于当有多个相同字符时以它们结尾的、内容相同的子序列会被重复累加。我们需要一种状态定义能够以“字符值”本身而不是“字符位置”作为区分从而自动合并相同子序列的贡献。3. 核心解法一以字符值为维度的动态规划既然重复来源于相同的字符那么我们就绕开“位置”直接以“字符”作为状态的一部分。这是解决此类去重计数问题的经典技巧。我们定义dp[x]表示以字符x结尾的、所有本质不同的上升子序列的个数。这里的x可以是’a’到’z’的26个小写字母根据题目字符集而定。现在我们按顺序遍历原字符串s的每一个字符s[i]。对于当前字符s[i]我们需要更新整个dp数组。思考一下s[i]的出现会对哪些状态产生影响它自身可以作为一个新的子序列所以以s[i]结尾的子序列数量至少可以增加1。即dp[s[i]] 1。它可以接在所有结尾字符小于它的子序列之后形成新的、更长的子序列对于所有字符k如果k s[i]按ASCII码比较那么所有以k结尾的子序列后面都可以加上s[i]形成一个新的以s[i]结尾的子序列。并且由于我们是以字符值区分的dp[k]已经代表了所有以k结尾的本质不同序列。所以这些新形成的序列也一定是本质不同的。因此dp[s[i]]应该增加sum(dp[k])其中k取所有小于s[i]的字符。但是这里有一个巨大的坑也是很多人在第一次推导时容易出错的地方直接累加会导致重复更新。假设字符串是”aba”我们一步步来看初始化dp[‘a’..’z’] 0。处理第一个字符’a’dp[‘a’] 1。此时dp[‘a’] 1序列”a”。处理第二个字符’b’所有小于’b’的字符是’a’。sum(dp[k]) dp[‘a’] 1。dp[‘b’] (1 1)等等这里1是sum(dp[k])另一个1是它自身。所以dp[‘b’] 2。序列是”b”和”ab”。正确。处理第三个字符’a’所有小于’a’的字符没有。所以sum(dp[k]) 0。dp[‘a’] (0 1)如果这样dp[‘a’]就变成了1 1 2。这表示以’a’结尾的序列有2个”a”(第一个) 和”a”(第三个)。但根据“本质不同”的定义这两个”a”是同一个序列我们重复计数了。问题出在哪当我们第二次遇到’a’时dp[‘a’]已经为1代表之前已经统计过以’a’结尾的序列即第一个’a’自身。现在这个新的’a’它自身作为一个序列”a”与之前统计过的”a”是本质相同的不应该重复加入。它唯一能贡献的是接在那些结尾小于’a’的序列后面但并没有这样的序列。所以对于当前字符s[i]它不应该简单地将“自身作为一个序列”加到dp[s[i]]中因为可能已经加过了。正确的更新策略应该是对于当前遍历到的字符s[i]我们计算一个add值它等于1 sum(dp[k])其中k取所有小于s[i]的字符。这个add值代表了以当前位置的s[i]作为结尾能够形成的、所有新的本质不同的上升子序列的数量。然后我们将这个add值加到dp[s[i]]上。注意是“加到”而不是“设为”。为什么考虑字符串”abab”。处理第一个’a’add 1dp[‘a’] 1。处理第一个’b’add 1 dp[‘a’] 2dp[‘b’] 2。处理第二个’a’add 1 0 1。如果我们将dp[‘a’]设为这个add值那就错了因为我们会丢失第一个’a’已经形成的序列”a”。实际上第二个’a’带来了一个新的序列”a”虽然本质与第一个相同但在这个算法逻辑里我们需要通过“加到”来让后续计算感知到它的存在吗不这里正是关键。让我们重新审视。dp[x]的定义是以字符 x 结尾的、所有本质不同的上升子序列的个数。 当第二个’a’出现时它能形成的、新的、以’a’结尾的本质不同序列有哪些序列”a”本身。但这个序列在第一个’a’出现时已经被记录在dp[‘a’]里了。所以它对于“本质不同”这个集合来说不是新的。它可以接在结尾小于’a’的序列后面。没有这样的序列。所以第二个’a’没有产生任何新的、本质不同的、以 ‘a’ 结尾的序列。因此它不应该对dp[‘a’]产生任何贡献dp[‘a’]应该保持为1。那么add 1 sum(dp[k])这个公式还适用吗它计算的是“以当前位置的字符作为结尾能形成的新序列数量”。对于第二个’a’这个值是1它自身。但如果我们把这个1加到dp[‘a’]上就重复了。所以我们不能直接加。我们需要一个辅助变量或者改变遍历顺序。一种更清晰、更正确的做法是在遍历字符s[i]时我们计算一个临时值temp它表示在考虑前i-1个字符后以s[i]这个字符结尾能够新增的序列数量。这个temp 1 sum(dp[k])。然后我们用这个temp去更新所有以s[i]结尾的未来状态吗不这不对。让我们换一种状态定义这是最终正确的解法定义dp[x]表示遍历到当前位置为止以字符x结尾的、所有本质不同的上升子序列的个数。状态转移顺序遍历字符串s。 对于当前字符ch s[i]我们计算一个new_add。它代表如果选择当前这个ch作为子序列的最后一个字符可以形成多少种新的序列。这些新序列来自两部分A. 序列只包含ch自身这总是1种。B. 在所有已经出现过的、以某个小于ch的字符结尾的序列后面追加ch。这部分的数量就是所有小于ch的字符k对应的dp[k]之和。所以new_add 1 sum(dp[k] for k in ‘a’..chr(ord(ch)-1))。然后我们更新dp[ch] new_add。注意这里是赋值而不是累加。为什么这里是赋值因为dp[ch]表示“以ch结尾的所有本质不同序列”。当遇到一个新的ch时之前可能已经有以ch结尾的序列了来自更早出现的ch。但是对于当前这个新出现的ch由它产生的序列和由之前出现的ch产生的序列如果内容相同就是本质相同的。而我们的new_add已经包含了所有可能的内容组合通过累加所有小于ch的dp[k]。如果之前有另一个ch已经形成过同样的序列那么这个序列一定是由某个小于ch的序列加上那个更早的ch形成的其数量已经包含在了之前计算dp[k]时所用的、更早的dp[ch]的贡献里了吗这个推理有点绕。让我们用”abac”来手动模拟一下这种“赋值”法初始化dp[‘a’..’z’]0。字符’a’(索引0):new_add 1 sum(dp[‘a’]) 1 0 1dp[‘a’] 1(序列:”a”)字符’b’(索引1):new_add 1 sum(dp[‘b’]) 1 dp[‘a’] 1 1 2dp[‘b’] 2(序列:”b”,”ab”)字符’a’(索引2):new_add 1 sum(dp[‘a’]) 1 0 1dp[‘a’] 1(序列:”a”)这里覆盖了字符’c’(索引3):new_add 1 sum(dp[‘c’]) 1 (dp[‘a’] dp[‘b’]) 1 (1 2) 4dp[‘c’] 4(序列:”c”,”ac”,”bc”,”abc”)最后所有本质不同的上升子序列总数 sum(dp[‘a’..’z’]) 1 2 4 7。与我们之前列举的{”a”, “b”, “c”, “ab”, “ac”, “bc”, “abc”}吻合。完美在这个模拟中第二个’a’出现时dp[‘a’]被更新为1。这看似覆盖了第一个’a’的贡献但请注意第一个’a’的贡献已经通过dp[‘a’]传递给了后面的’b’和’c’在计算’b’和’c’的new_add时sum(dp[‘b’])和sum(dp[‘c’])都包含了当时的dp[‘a’]值。当第二个’a’出现时它自身作为序列”a”并没有带来新的本质不同序列所以dp[‘a’]被重置为1是合理的它只代表“以字符 ‘a’ 结尾的序列”这个集合而这个集合里始终只有”a”这一个元素。覆盖操作实际上避免了重复计算同一个序列”a”。因此解法一的核心状态转移方程为 遍历字符串s的每个字符chdp[ord(ch)] 1 sum(dp[0:ord(ch)])这里dp数组下标对应字符的ASCII码例如dp[97]对应’a’。 最后答案ans sum(dp)。注意在具体实现时sum(dp[0:ord(ch)])需要快速计算否则时间复杂度是O(26*n)虽然对于n200可以接受但不够优美。我们可以维护一个前缀和数组prefix_sumprefix_sum[x]表示所有 ASCII 码小于等于x的字符对应的dp值之和。这样sum(dp[0:ord(ch)])就等于prefix_sum[ord(ch)-1]。每更新一个dp[ch]就需要更新从ch到’z’的prefix_sum。这样可以将复杂度优化到O(26*n)常数很小。4. 核心解法二集合去重思想的动态规划第一种解法从字符维度出发非常巧妙。还有一种理解方式可能更符合直觉我们直接维护“以每个位置结尾的本质不同序列集合”但通过巧妙的更新顺序来去重。定义dp[i]一个集合或更高效地一个计数器表示以字符串第i个字符s[i]结尾的、所有本质不同的上升子序列。但存储集合本身在编程中很耗时我们可以存储这些序列的个数以及它们的一个“特征”来帮助去重。实际上解法一已经隐含了这种思想。我们可以这样理解解法二初始化一个长度为n的数组dpdp[i]初始为1表示序列s[i]自身。我们按顺序i 0 to n-1遍历每个位置。对于每个位置i我们再遍历它之前的所有位置j (0 j i)。如果s[j] s[i]那么所有以s[j]结尾的本质不同子序列后面都可以加上s[i]形成新的以s[i]结尾的子序列。所以dp[i]应该加上dp[j]。但是这里依然有重复问题如果存在j1和j2(j1 j2 i)且s[j1] s[j2]那么以s[j1]和s[j2]结尾的序列集合中可能会有大量重复的序列只要它们的内容相同。直接加dp[j1]和dp[j2]就会导致重复。如何避免关键在于当我们在位置i遇到字符ch时对于所有在i之前出现的、同样是ch的字符我们只应该考虑最近一次出现的那个ch所带来的贡献。为什么因为更早出现的ch所能形成的序列最近一次出现的ch也都能形成通过选择更晚的位置并且由于字符相同它们形成的序列内容是完全一样的。如果我们累加了更早的ch的贡献就会重复计算那些内容相同的序列。因此解法二的算法步骤如下初始化一个长度为n的数组dpdp[i] 1。初始化一个长度为26或字符集大小的数组lastlast[x] -1用于记录字符x最近一次出现的位置。遍历i从0到n-1ch s[i]dp[i] 1自身作为一个序列遍历j从0到i-1如果s[j] chdp[i] dp[j]但是如果存在k使得j k i且s[j] s[k]即s[j]这个字符在j之后又出现了那么dp[j]中对dp[i]的贡献实际上会被dp[k]覆盖。更精确地说我们应该在累加时只累加每个字符“最后一次出现”时的dp值。更新last[ch] i这个描述中的内层循环仍然有重复累加的风险。更精确的实现是 在计算dp[i]时我们不再遍历所有j i而是遍历所有可能的字符c’a’到比s[i]小的字符。 对于每个字符c如果它最近一次出现的位置last[c] ! -1那么dp[i] dp[last[c]]。 这样对于每个小于s[i]的字符我们只取它最后一次出现时所能形成的所有序列。这就保证了从相同字符转移到s[i]时序列是唯一的。然后我们需要更新dp[i]吗实际上dp[i]就是通过上述累加得到的再加上自身的1。最后更新last[s[i]] i并且将dp[i]赋值给一个全局的、以字符s[i]为索引的数组char_dp即char_dp[ord(s[i])] dp[i]。这样char_dp[x]始终保存了字符x最后一次出现时以它结尾的序列总数。你会发现这个char_dp数组最终的状态和含义与解法一中的dp数组是完全一致的。解法二是从位置视角出发通过“只取最后一次出现”的规则来去重最终收敛到字符视角。解法一则是直接站在字符视角进行状态定义和转移更加简洁直观。在竞赛中解法一的代码实现更为简单不易出错。下面给出解法一的Python实现代码及详细注释。MOD 10**9 7 # 常见的取模值 def count_distinct_increasing_subsequences(s: str) - int: 计算字符串 s 中本质不同的上升子序列的个数。 上升子序列要求每个字符的ASCII码严格大于前一个字符。 # dp数组下标对应字符的ASCII码这里假设字符串只包含小写字母 # 为了清晰我们使用长度为26的数组索引0对应a25对应z dp [0] * 26 for ch in s: idx ord(ch) - ord(a) # 将字符映射到0-25的索引 # 计算 new_add: 1 (自身) 所有结尾字符小于 ch 的序列数之和 total 1 # 初始化为1代表序列只包含 ch 自身 for i in range(idx): # 遍历所有小于当前字符的字符 total (total dp[i]) % MOD # 关键步骤赋值而不是累加 dp[idx] total # 答案是所有以某个字符结尾的序列数之和 ans 0 for cnt in dp: ans (ans cnt) % MOD return ans # 测试用例 if __name__ __main__: # 示例1: abac print(count_distinct_increasing_subsequences(abac)) # 应输出 7 # 示例2: aaa (没有上升序列只有单个a且本质相同) print(count_distinct_increasing_subsequences(aaa)) # 应输出 1 # 示例3: abc print(count_distinct_increasing_subsequences(abc)) # 应输出 7 (a,b,c,ab,ac,bc,abc)5. 算法优化与细节剖析上面的基础实现时间复杂度是O(26 * n)对于n200完全足够。但如果我们追求极致的效率或者字符集更大比如包含大小写字母和数字我们可以进行优化。优化点一快速计算前缀和在循环for i in range(idx): total dp[i]中我们每次都在累加dp[0]到dp[idx-1]的和。这是一个典型的前缀和查询。我们可以维护一个前缀和数组prefix其中prefix[i]表示dp[0] dp[1] ... dp[i]的和对MOD取模后。那么total 1 (prefix[idx-1] if idx 0 else 0)。 更新dp[idx] total后我们需要更新prefix数组从idx到末尾的所有值因为prefix[j] (j idx)都包含了dp[idx]。这个更新如果逐个进行又是O(26)。我们可以采用差分思想但更简单直接的方法是在计算出total后我们直接更新dp[idx]然后在所有循环结束后再计算一次前缀和作为答案不我们需要在循环内更新前缀和以供下一个字符使用。一个更巧妙的做法是不显式维护prefix数组而是在遍历字符串时动态维护一个变量cur_sum表示当前所有dp值的和。但是当我们要计算小于ch的dp值和时需要的是“更新当前字符之前的dp值之和”。由于dp值会被覆盖cur_sum不能直接使用。实际上对于这道题O(26*n)的复杂度已经足够优秀且代码清晰。优化前缀和带来的常数提升对于200的长度微乎其微。代码的清晰性和正确性优先级更高。优化点二处理大字符集如果字符集不是26个小写字母而是整个ASCII码128或256我们的dp数组长度相应变大但算法逻辑完全不变。时间复杂度变为O(m * n)其中m是字符集大小。在字符集很大时比如UnicodeO(m*n)可能不可接受。此时我们需要用更高效的数据结构来查询“所有小于当前字符的dp值之和”比如树状数组Fenwick Tree或线段树Segment Tree。它们可以在O(log m)的时间内完成区间求和与单点更新操作从而将总复杂度降至O(n log m)。这在蓝桥杯国赛难度中属于超纲内容但了解这种优化思路对解决更广泛的计数问题很有帮助。关键细节取模运算题目通常要求结果对一个大质数如10^97取模。在代码中每次加法运算后都应立即取模防止整数溢出。Python本身支持大整数但取模可以保证结果在要求范围内并且是良好的编程习惯。一个容易忽略的边界空序列算不算在经典的子序列问题中空序列即一个字符都不选通常不被计入。本题的“上升子序列”隐含了序列至少包含一个字符因为上升需要比较空序列或单字符序列通常也被认为是“上升”的但单字符序列在本算法中通过total1已经计入。我们的算法没有计入空序列符合题意。如果题目明确要求包含空序列只需在最终答案上加1即可。6. 竞赛实战技巧与常见错误在紧张的竞赛环境中理解和实现这个算法需要避免以下几个坑状态转移方程写成累加这是最常见的错误。看到dp[ch] 1 sum(...)就觉得对了。一定要记住对于相同字符新出现的字符会“重置”以该字符结尾的序列集合所以是赋值不是累加。你可以这样记忆dp[x]始终代表“最后一次遇到字符x时以它结尾的序列总数”。初始化错误dp数组应初始化为0。有些同学可能想初始化dp[ch] 1这是不对的因为字符还没出现。忽略取模在计算total和最终答案时忘记取模导致可能输出负数在某些语言中或者数字过大。字符到索引的映射题目明确是小写字母用ord(ch)-ord(‘a’)是安全的。如果字符集不明需要先确认范围。理解“本质不同”始终用”abac”这样有重复字符的例子来验证你的算法。手动模拟前几步确保第二个’a’不会导致”a”被计算两次并且”ac”这样的序列只被计算一次。测试用例设计单字符字符串”a”答案应为1。全相同字符”aaa”答案应为1只有单个字符’a’这一种子序列。严格递增字符串”abc”答案应为2^3 - 1 7所有非空子序列都满足上升条件。包含递减的字符串”cba”答案应为3只有单个字符’c’,’b’,’a’。混合字符串”abac”答案应为7。在考场上如果你一下子想不出最优解可以尝试从暴力DFS集合去重开始思考然后意识到需要DP再思考如何定义状态才能去重。把“本质不同”转化为“以字符结尾”是一个关键的思维跳跃点。最后这类“带去重条件的子序列计数”问题有一个通用的思考框架如果重复来源于相同的元素那么状态定义尽量避开“位置”而使用“值”作为维度。类似的题目还有统计本质不同的子序列个数不要求上升其状态定义和转移也有异曲同工之妙。掌握这个思想就能举一反三。