1. 项目概述从一道国赛真题看动态规划的本质最近在复盘蓝桥杯的历年真题特别是国赛级别的题目总能发现一些将经典算法思想包装得极其巧妙的案例。今天想和大家深入聊聊2020年第十一届国赛的这道“本质上升序列”问题。初次看到这个标题很多同学可能会联想到经典的“最长上升子序列”LIS问题觉得无非是动态规划DP的又一次应用。但“本质”二字恰恰是这道题设下的精妙陷阱它要求我们不仅要求出上升子序列的数量还要剔除那些虽然字符顺序不同但内容重复的序列。这就像让你数一数一片森林里有多少棵形态各异的树而不是简单地统计所有树木的数量——重复的树种只算一次。这道题完美地考察了选手对动态规划状态定义深刻性的理解以及如何在此基础上进行去重处理是区分算法“熟练工”和“思考者”的一道分水岭。对于正在备赛蓝桥杯尤其是冲击国奖的同学来说吃透这道题的价值远超题目本身。它训练的不是套模板的能力而是根据问题本质重新设计和修正模型的能力。这种能力在解决未知的、复杂的工程问题时至关重要。接下来我将彻底拆解这道题从最朴素的暴力思路开始一步步推导到最优的动态规划解法并分享我在调试和优化过程中踩过的坑和总结的心得。2. 问题核心与暴力思路解析2.1 问题重述与关键点剖析题目通常会给一个字符串例如蓝桥杯真题中的lanqiao要求我们计算该字符串中“本质不同的上升子序列”的个数。我们需要明确几个关键概念子序列从原字符串中按原始顺序取出一些字符可以不连续组成的新序列。例如对于abca,ac,b都是它的子序列但ca不是。上升子序列在此题语境下“上升”通常指字典序严格递增。即对于子序列s[i], s[j]若i j则必须有s[i] s[j]字符的ASCII码比较。这保证了序列中的字符是严格从左到右增大的。本质不同这是本题的难点。两个子序列即使由原字符串中不同位置的字符组成只要它们最终形成的字符串完全相同就被视为同一个“本质”。例如字符串aba中取第一个a和最后一个a可以形成子序列aa取第一个a和中间的b形成ab取中间的b和最后一个a也形成ba。但如果我们考虑所有上升子序列并去重情况就复杂了。一个最直观的暴力方法是生成字符串的所有可能子序列检查每个子序列是否是严格上升的如果是则将其加入一个集合Set进行自动去重最后返回集合的大小。对于一个长度为n的字符串其子序列总数为2^n个每个字符有“选”或“不选”两种状态。当n较大时比如n2002^200是一个天文数字这种指数级复杂度是完全不可接受的。因此暴力枚举只能帮助我们理解题意绝非正解。2.2 动态规划的初步联想与陷阱既然暴力不行我们自然想到用动态规划来优化。经典的“最长上升子序列LIS”问题的动态规划思路是定义dp[i]表示以第i个字符结尾的最长上升子序列的长度。其状态转移方程为dp[i] max(dp[j]) 1其中j i且s[j] s[i]。这个模型解决的是“长度”问题。而我们本题要求的是“数量”并且是“本质不同的数量”。一个直接的错误想法是模仿LIS定义dp[i]为以s[i]结尾的本质不同上升子序列的个数。然后尝试累加所有dp[i]。为什么这样不行呢考虑字符串abab。以第一个b索引1结尾的上升子序列有b,ab。以第二个b索引3结尾的上升子序列如果简单地从前面所有小于b的字符a在索引0和2后面转移过来我们会得到b,ab从索引0的a来ab从索引2的a来。这里ab就被重复计算了因为虽然来自原串不同位置的a但形成的子序列字符串都是ab。所以简单的dp[i]累加会重复计算那些由不同位置但相同字符结尾所形成的、且中间序列也相同的子序列。问题的根源在于我们的状态dp[i]只记录了“以位置i结尾”而没有识别出“以字符s[i]结尾且序列内容为某一特定字符串”这个更精确的本质。我们需要一种方法来合并这些重复项。3. 正解基于字符尾部的动态规划3.1 状态定义的巧妙转变为了规避重复计数我们必须改变状态定义的角度。经典LIS的dp[i]是以“位置”为维度这在本问题中导致了信息冗余多个位置可能产生相同的序列。一个更高效的角度是以“字符”为维度。我们定义dp[c]表示以字符c结尾的、所有本质不同的上升子序列的个数。这里c的取值范围是字符串中出现的字符通常考虑小写字母a到z。这个定义一下子就把关注点从“哪个位置的字符”转移到了“哪个字符”本身。无论原字符串中有多少个a所有以a结尾的本质不同序列都统一归到dp[a]这个状态里。3.2 状态转移方程的推导现在我们从左到右遍历原字符串s的每一个字符s[i]。假设当前遍历到字符ch s[i]。对于dp[ch]的更新我们需要考虑所有可以接在ch前面的、字典序比ch小的字符prev。所有以prev结尾的上升子序列在后面添加上当前的ch就构成了新的、以ch结尾的上升子序列。因此转移方程的核心部分是dp[ch] sum(dp[prev])其中prev遍历所有比ch小的字符。但这还不够。我们还需要考虑子序列ch本身即只包含当前一个字符的序列。它也是一个合法的、以ch结尾的上升子序列。所以每次遇到字符ch我们至少应该给dp[ch]增加1。然而直接这样加又会遇到重复问题。假设字符串是aa。遍历第一个a时dp[a] 1序列a。遍历第二个a时按照上述逻辑sum(dp[prev])对于a来说没有比它小的prev所以这部分为0。然后加上单字符序列1得到dp[a] 1此时dp[a]变成了2。但这显然不对因为以a结尾的本质不同上升子序列只有a这一个。第二个a产生的序列a与第一个产生的完全一样被重复计数了。3.3 关键去重增量更新与最后位置记录问题的关键在于当我们在字符串中再次遇到同一个字符ch时我们不能简单地给dp[ch]加1也不能简单地把前面所有dp[prev]累加过来。因为之前遇到ch时已经计算过一部分以ch结尾的序列了再次累加会导致历史序列被重复计算。正确的做法是在遍历每个字符ch时我们计算一个“增量”这个增量代表了“由当前这个新出现的ch所产生的新序列”的数量。然后我们用这个增量去更新dp[ch]。如何计算这个增量首先这个增量必须包含由当前字符单独构成的序列1。其次它可以接在所有比ch小的字符prev所结尾的序列后面。但是这里累加的应该是prev字符对应的、截止到遍历当前字符之前的总方案数。注意不是dp[prev]的当前值因为dp[prev]可能包含了更早之前由其他ch更新时产生的影响我们需要的是一个“基准值”。实际上更清晰且不易出错的做法是引入一个辅助的“总方案数”数组。但有一个经典的技巧在遍历过程中我们维护一个total数组total[c]表示遍历到当前位置时以字符c结尾的所有本质不同上升子序列的总数。当我们处理新的字符s[i] ch时我们计算add 1 sum(total[prev]) for prev ch。这个add就是由当前这个ch带来的全新序列的数量。然后我们更新total[ch] add。为什么这样能去重因为对于同一个字符ch每次遇到它我们都基于当前时刻所有比它小的字符的总方案数来计算新增量。之前由同一个字符ch产生的序列已经包含在total[prev]的历史累计值中不会在本次计算add时被再次作为“前缀”使用。而add只包含本次新字符产生的新组合。最终整个字符串中所有本质不同的上升子序列总数就是sum(total[c])对所有字符c求和。3.4 算法流程与示例演算让我们用字符串abab来手动演算一下定义total[0..25]对应a到z初始全为0。遍历s[0] a(索引0)比a小的字符没有所以sum_prev 0。add 1 0 1。更新total[a] 1。此时total[a]1其他为0。解释新增了序列a。遍历s[1] b(索引1)比b小的字符有asum_prev total[a] 1。add 1 1 2。更新total[b] 2。此时total[a]1,total[b]2。解释新增了序列b和ab。其中ab是由已有的a后面添加b构成。遍历s[2] a(索引2)比a小的字符没有sum_prev 0。add 1 0 1。更新total[a] 1。此时total[a]2,total[b]2。解释注意这里add是1只新增了序列a吗不对索引2的a和索引0的a形成的序列都是a是同一个本质。所以实际上这次更新没有产生任何新序列。我们的算法哪里出问题了问题暴露我们重复计算了单个字符a。当第二次遇到a时add1代表的新序列a已经存在了。我们的去重逻辑只防止了多字符序列的重复通过依赖total[prev]但没有防止单字符序列的重复。3.5 修正处理单字符重复的最终方案上述演算揭示了我们方案的最后一道障碍如何避免同一个字符形成的单字符子序列被多次计数解决方法其实很简单我们不再将“单字符序列”这个1直接加到add里而是换一种方式初始化。我们可以这样理解所有本质不同的单字符序列就是字符串中出现的不同字符的集合。我们可以在开始动态规划之前就处理好它。修正后的算法流程初始化一个长度为26的数组dp所有元素为0。dp[c]表示以字符c结尾的所有本质不同上升子序列的个数。遍历字符串s的每个字符ch a. 计算增量add 0。 b. 对于所有比ch小的字符prev执行add dp[prev]。这表示当前ch可以接在所有以prev结尾的序列后面形成新序列。 c. 现在add代表了“由当前字符ch与前面更小的字符结尾的序列结合所产生的新序列”的数量。 d. 关键步骤将增量add加到dp[ch]上即dp[ch] add。遍历结束后将所有dp[c]求和得到的结果就是所有长度大于等于2的本质不同上升子序列的数量。最后再加上字符串中不同字符的个数即所有长度为1的本质不同上升子序列。为什么步骤4是加不同字符的个数因为在我们的动态规划过程中dp[ch]的初始值是0。当第一次遇到字符ch时add的计算基于dp[prev]而初始时dp[prev]都是0所以第一次遇到的ch产生的add为0。这意味着我们的dp数组从一开始就没有计入任何单字符序列。单字符序列在“上升”的定义下是平凡的没有前驱字符我们单独计算它们即可。让我们用修正后的算法重新演算abab初始化dp[a]0, dp[b]0。遍历a(索引0)add 0dp[a] 0-dp[a]0。遍历b(索引1)比b小的字符有aadd dp[a] 0dp[b] 0-dp[b]0。遍历a(索引2)add 0dp[a] 0-dp[a]0。遍历b(索引3)比b小的字符有aadd dp[a] 0dp[b] 0-dp[b]0。结束后dp总和为0。字符串中不同字符为{a, b}数量为2。最终结果 0 2 2。验证一下abab的本质不同上升子序列有a,b,ab。等等怎么是3个我们的算法结果2不对ab漏掉了。问题又出在哪里3.6 最终正确的动态规划转移我们离成功只差最后一步了。修正后的算法漏掉了形如ab这样的序列。原因是当我们处理第二个字符b索引1时add的计算依赖于dp[a]而dp[a]在此时仍然是0因为我们第一次遇到a时没有增加任何序列。所以b无法与前面的a结合形成ab。症结在于我们的dp状态应该包含以某个字符结尾的所有序列包括单字符序列。但我们又不想重复计算单字符序列。一个完美的解决方案是在遍历每个字符时我们计算出的add已经包含了由当前字符新构成的所有序列包括接在前驱序列后面的和它自己单独构成的。然后我们用这个add去更新所有大于等于当前字符的dp值吗不这样不对。让我们回归最朴素但正确的思路并用一个例子abc来推导 我们定义dp[i]表示以s[i]结尾的本质不同上升子序列的个数注意这里又回到了以位置结尾但我们会处理重复。当我们计算dp[i]时dp[i] 1 sum(dp[j])其中j i且s[j] s[i]。 这里的1代表子序列s[i]自身。sum(dp[j])代表所有以小于s[i]的字符结尾的序列后面加上s[i]。 但这样会有重复比如aba中两个a结尾的序列会重复。为了去重我们观察到一个重要性质如果当前字符s[i]之前出现过设上一次出现的位置是last那么所有以s[last]结尾的序列都可以被当前这个s[i]重新构造出来这部分是重复的。更准确地说当计算dp[i]时我们应该减去那些已经被前一个相同字符计算过的、以更小字符结尾的序列贡献。因此正确的状态转移方程是 令last[c]记录字符c上一次出现时的dp值即以该位置结尾的序列总数。 当遍历到s[i] ch时计算add 1 sum(dp[j] for j in range(i) if s[j] ch)。这个add是以当前位置i的字符ch结尾的、所有可能的序列数包含新旧。那么本次新增的、不重复的序列数应该是add - last[ch]。因为last[ch]代表了上一次遇到ch时已经计算过的、以ch结尾的序列数这些序列在这次会被重复构造。更新dp[i] add - last[ch]。更新last[ch] add为下一次遇到ch做准备。最终答案就是所有dp[i]的和。对于abab初始化dp数组和last字典记录字符上次的add值初始为0。i0, chaadd 1 0 1。last[a]0。dp[0] 1 - 0 1。last[a] 1。i1, chbadd 1 dp[0] (因为 s[0]a b) 112。last[b]0。dp[1] 2 - 0 2。last[b] 2。新增序列b,abi2, chaadd 1 0 1前面没有比a小的字符。last[a]1。dp[2] 1 - 1 0。last[a] 1。没有新增序列因为单字符a已存在i3, chbadd 1 dp[0] dp[2] (s[0]和s[2]都是a且都小于b) 1 1 0 2。last[b]2。dp[3] 2 - 2 0。last[b] 2。没有新增序列因为b和ab都已存在总和sum(dp) 1 2 0 0 3。符合预期a,b,ab。这个算法的时间复杂度是 O(n * alphabet_size)对于小写字母alphabet_size26所以是 O(26n)效率非常高。空间复杂度为 O(n 26)。4. 代码实现与细节处理理解了上述推导过程代码实现就相对清晰了。以下是用Python实现的示例代码包含了详细的注释def count_distinct_increasing_subsequences(s: str) - int: 计算字符串 s 中本质不同的严格上升子序列的个数。 严格上升指字典序递增。 n len(s) if n 0: return 0 # dp[i] 表示以 s[i] 结尾的本质不同上升子序列的个数本次新增 dp [0] * n # last_add[char] 记录字符 char 上一次出现时计算出的总 add 值。 # 初始化为0表示该字符还未出现过。 last_add [0] * 128 # 使用ASCII码范围简单通用。也可用字典。 for i in range(n): ch s[i] # 1. 计算 add1(自身) 前面所有小于 ch 的字符结尾的序列总数 add 1 for prev_char in range(ord(a), ord(ch)): # 遍历所有比 ch 小的字符 # 注意这里累加的是该字符上一次出现时的总 add 值。 # 这个值代表了截止到上一次出现该字符时以它结尾的所有序列数。 # 这些序列都可以在后面接上当前的 ch。 add last_add[prev_char] # 2. 本次新增的、不重复的序列数 add - 上一次该字符的总序列数 dp[i] add - last_add[ord(ch)] # 3. 更新该字符的最后总序列数记录 last_add[ord(ch)] add # 最终答案是所有 dp[i] 之和 return sum(dp) # 测试用例 if __name__ __main__: print(count_distinct_increasing_subsequences(abab)) # 应输出 3 print(count_distinct_increasing_subsequences(lanqiao)) # 可以测试真题数据代码关键点解析与注意事项last_add数组的含义它存储的是字符c在上一次出现时计算出的add值。这个add值代表的是截止到上一次出现位置以字符c结尾的所有本质不同序列的数量包括单字符c自身。这是去重的核心。内层循环for prev_char in range(ord(a), ord(ch)):这里遍历的是所有ASCII码值小于当前字符ch的字符。我们累加的是这些字符对应的last_add值。为什么是last_add而不是当前时刻以它们结尾的序列总数因为last_add[prev_char]已经包含了截止到该字符最后一次出现时所有以它结尾的序列。之后如果再出现相同的prev_char新产生的序列会更新last_add[prev_char]从而在后续计算中被包含进去。这种设计保证了我们总是基于最新的、完整的“前缀”集合来生成新序列。dp[i]的计算dp[i] add - last_add[ord(ch)]。add是理论上以当前字符ch结尾能形成的所有序列数包括重复的。last_add[ord(ch)]是上一次遇到ch时已经计算过的序列数。两者相减得到的就是本次新出现的、不重复的序列数量。初始化last_add初始为0是合理的表示每个字符在首次出现前其历史序列数为0。字符范围代码中使用了last_add[128]覆盖了ASCII码的基本范围。如果题目明确只有小写字母可以优化为last_add[26]通过ord(ch) - ord(a)来索引效率更高。大数处理蓝桥杯真题的字符串可能很长结果可能非常大需要关注题目要求的数据类型。在Python中整数可以自动处理大数但在C/Java中可能需要使用long long或高精度计算。5. 常见错误与调试心得在理解和实现这道题的过程中我以及我见过的很多同学都容易踩进以下几个坑坑1混淆“位置”和“字符”维度最初总想着用dp[i]直接表示以位置i结尾的总数然后求和。这必然导致重复计数因为不同位置可能产生相同的序列。必须意识到去重需要我们将状态从“位置”聚合到“字符”层面或者像最终解法一样在“位置”维度上进行精细的重复项减除。坑2忽略单字符序列的去重这是最隐蔽的坑。当我们用“增量更新”的思路时很容易忘记单字符序列a在字符串中出现多次时只应被计算一次。我们的最终解法通过dp[i] add - last_add[ch]巧妙地处理了这个问题因为对于第一次出现的字符last_add[ch]0dp[i]add包含了1它自身对于第二次出现的相同字符上次的add包含了1被减去从而抵消了新增的单字符序列。坑3错误理解last_add的更新时机last_add[ch]必须在计算完本次的dp[i]后才更新为新的add值。如果先更新last_add再计算dp[i]就会导致dp[i] add - add 0完全错误。顺序是计算add- 计算dp[i]- 更新last_add[ch] add。坑4内层循环累加对象错误在内层循环累加“前缀”序列数时是累加last_add[prev_char]而不是dp[某个位置]。因为last_add[prev_char]代表了以字符prev_char结尾的所有历史序列总和这正是当前字符ch可以接在后面形成新序列的“基础数量”。调试建议从小例子开始像a,aa,ab,aba,abab这样的短字符串手工计算出所有本质不同上升子序列然后单步调试你的程序观察dp和last_add数组的变化是否与你的手动推导一致。打印中间变量在循环中打印i,ch,add,dp[i],last_add[ord(ch)]的值对于理解数据流非常有帮助。对比两种理解将“以位置结尾”和“以字符结尾”两种动态规划思路的中间结果都打印出来对比它们的差异能深刻理解去重的本质。6. 算法扩展与相关真题链接掌握了“本质上升序列”的解法其实就掌握了一类“带去重的子序列计数”问题的核心思想。这个思想可以扩展到更多场景修改上升规则如果不是严格字典序递增而是非递减即允许相等状态转移中的比较条件s[j] s[i]就需要改为s[j] s[i]同时去重逻辑要更加小心因为相同字符连续出现时序列aa也应该被允许。计数模一个大数蓝桥杯题目经常要求结果对1e97取模。我们只需要在每次加法运算add last_add[prev_char]和dp[i] add - last_add[ch]后加上取模操作即可。注意减法后可能得到负数需要(add - last MOD) % MOD来调整。与最长上升子序列LIS问题的关系这是动态规划的经典入门题。LIS求的是最大长度通常用dp[i]表示以i结尾的LIS长度用二分查找优化可以达到 O(n log n)。而本题求的是去重后的序列总数维度不同优化思路也不同。将两者对比学习能更好地理解DP状态设计如何影响问题复杂度。在蓝桥杯真题库中与此题思想相关的题目还有“不同的子序列”给定一个字符串s和一个字符串t计算在s的子序列中t出现的个数。这也是一个经典的动态规划计数问题状态通常定义为dp[i][j]表示s的前i个字符中t的前j个字符出现的次数。其转移方程也涉及去重思想当s[i-1] t[j-1]时可以选择匹配或不匹配。“上升子序列和”求所有上升子序列的最大和。这又是一种变体状态dp[i]表示以i结尾的上升子序列的最大和转移方程为dp[i] max(dp[i], dp[j] s[i])当s[j] s[i]。这道“本质上升序列”题就像一把钥匙打开了用动态规划解决复杂计数问题的大门。它告诉我们面对计数问题尤其是涉及“本质不同”的去重时单纯枚举然后去重是行不通的必须在状态转移的过程中就嵌入去重的逻辑。而实现这一点的关键往往在于寻找一个恰当的状态定义以及维护额外的信息如last_add来记录历史从而在计算增量时能够精确地剔除重复部分。在平时练习时不妨多找几道类似的计数DP题目反复体会这种“在过程中去重”的思想这对于提升竞赛水平和解决实际编程问题都大有裨益。 
长河君 · 2026/8/28 14:33:01 · 阅读 1.2k 动态规划去重计数：从最长上升子序列到本质上升序列
1. 项目概述从一道国赛真题看动态规划的本质最近在复盘蓝桥杯的历年真题特别是国赛级别的题目总能发现一些将经典算法思想包装得极其巧妙的案例。今天想和大家深入聊聊2020年第十一届国赛的这道“本质上升序列”问题。初次看到这个标题很多同学可能会联想到经典的“最长上升子序列”LIS问题觉得无非是动态规划DP的又一次应用。但“本质”二字恰恰是这道题设下的精妙陷阱它要求我们不仅要求出上升子序列的数量还要剔除那些虽然字符顺序不同但内容重复的序列。这就像让你数一数一片森林里有多少棵形态各异的树而不是简单地统计所有树木的数量——重复的树种只算一次。这道题完美地考察了选手对动态规划状态定义深刻性的理解以及如何在此基础上进行去重处理是区分算法“熟练工”和“思考者”的一道分水岭。对于正在备赛蓝桥杯尤其是冲击国奖的同学来说吃透这道题的价值远超题目本身。它训练的不是套模板的能力而是根据问题本质重新设计和修正模型的能力。这种能力在解决未知的、复杂的工程问题时至关重要。接下来我将彻底拆解这道题从最朴素的暴力思路开始一步步推导到最优的动态规划解法并分享我在调试和优化过程中踩过的坑和总结的心得。2. 问题核心与暴力思路解析2.1 问题重述与关键点剖析题目通常会给一个字符串例如蓝桥杯真题中的lanqiao要求我们计算该字符串中“本质不同的上升子序列”的个数。我们需要明确几个关键概念子序列从原字符串中按原始顺序取出一些字符可以不连续组成的新序列。例如对于abca,ac,b都是它的子序列但ca不是。上升子序列在此题语境下“上升”通常指字典序严格递增。即对于子序列s[i], s[j]若i j则必须有s[i] s[j]字符的ASCII码比较。这保证了序列中的字符是严格从左到右增大的。本质不同这是本题的难点。两个子序列即使由原字符串中不同位置的字符组成只要它们最终形成的字符串完全相同就被视为同一个“本质”。例如字符串aba中取第一个a和最后一个a可以形成子序列aa取第一个a和中间的b形成ab取中间的b和最后一个a也形成ba。但如果我们考虑所有上升子序列并去重情况就复杂了。一个最直观的暴力方法是生成字符串的所有可能子序列检查每个子序列是否是严格上升的如果是则将其加入一个集合Set进行自动去重最后返回集合的大小。对于一个长度为n的字符串其子序列总数为2^n个每个字符有“选”或“不选”两种状态。当n较大时比如n2002^200是一个天文数字这种指数级复杂度是完全不可接受的。因此暴力枚举只能帮助我们理解题意绝非正解。2.2 动态规划的初步联想与陷阱既然暴力不行我们自然想到用动态规划来优化。经典的“最长上升子序列LIS”问题的动态规划思路是定义dp[i]表示以第i个字符结尾的最长上升子序列的长度。其状态转移方程为dp[i] max(dp[j]) 1其中j i且s[j] s[i]。这个模型解决的是“长度”问题。而我们本题要求的是“数量”并且是“本质不同的数量”。一个直接的错误想法是模仿LIS定义dp[i]为以s[i]结尾的本质不同上升子序列的个数。然后尝试累加所有dp[i]。为什么这样不行呢考虑字符串abab。以第一个b索引1结尾的上升子序列有b,ab。以第二个b索引3结尾的上升子序列如果简单地从前面所有小于b的字符a在索引0和2后面转移过来我们会得到b,ab从索引0的a来ab从索引2的a来。这里ab就被重复计算了因为虽然来自原串不同位置的a但形成的子序列字符串都是ab。所以简单的dp[i]累加会重复计算那些由不同位置但相同字符结尾所形成的、且中间序列也相同的子序列。问题的根源在于我们的状态dp[i]只记录了“以位置i结尾”而没有识别出“以字符s[i]结尾且序列内容为某一特定字符串”这个更精确的本质。我们需要一种方法来合并这些重复项。3. 正解基于字符尾部的动态规划3.1 状态定义的巧妙转变为了规避重复计数我们必须改变状态定义的角度。经典LIS的dp[i]是以“位置”为维度这在本问题中导致了信息冗余多个位置可能产生相同的序列。一个更高效的角度是以“字符”为维度。我们定义dp[c]表示以字符c结尾的、所有本质不同的上升子序列的个数。这里c的取值范围是字符串中出现的字符通常考虑小写字母a到z。这个定义一下子就把关注点从“哪个位置的字符”转移到了“哪个字符”本身。无论原字符串中有多少个a所有以a结尾的本质不同序列都统一归到dp[a]这个状态里。3.2 状态转移方程的推导现在我们从左到右遍历原字符串s的每一个字符s[i]。假设当前遍历到字符ch s[i]。对于dp[ch]的更新我们需要考虑所有可以接在ch前面的、字典序比ch小的字符prev。所有以prev结尾的上升子序列在后面添加上当前的ch就构成了新的、以ch结尾的上升子序列。因此转移方程的核心部分是dp[ch] sum(dp[prev])其中prev遍历所有比ch小的字符。但这还不够。我们还需要考虑子序列ch本身即只包含当前一个字符的序列。它也是一个合法的、以ch结尾的上升子序列。所以每次遇到字符ch我们至少应该给dp[ch]增加1。然而直接这样加又会遇到重复问题。假设字符串是aa。遍历第一个a时dp[a] 1序列a。遍历第二个a时按照上述逻辑sum(dp[prev])对于a来说没有比它小的prev所以这部分为0。然后加上单字符序列1得到dp[a] 1此时dp[a]变成了2。但这显然不对因为以a结尾的本质不同上升子序列只有a这一个。第二个a产生的序列a与第一个产生的完全一样被重复计数了。3.3 关键去重增量更新与最后位置记录问题的关键在于当我们在字符串中再次遇到同一个字符ch时我们不能简单地给dp[ch]加1也不能简单地把前面所有dp[prev]累加过来。因为之前遇到ch时已经计算过一部分以ch结尾的序列了再次累加会导致历史序列被重复计算。正确的做法是在遍历每个字符ch时我们计算一个“增量”这个增量代表了“由当前这个新出现的ch所产生的新序列”的数量。然后我们用这个增量去更新dp[ch]。如何计算这个增量首先这个增量必须包含由当前字符单独构成的序列1。其次它可以接在所有比ch小的字符prev所结尾的序列后面。但是这里累加的应该是prev字符对应的、截止到遍历当前字符之前的总方案数。注意不是dp[prev]的当前值因为dp[prev]可能包含了更早之前由其他ch更新时产生的影响我们需要的是一个“基准值”。实际上更清晰且不易出错的做法是引入一个辅助的“总方案数”数组。但有一个经典的技巧在遍历过程中我们维护一个total数组total[c]表示遍历到当前位置时以字符c结尾的所有本质不同上升子序列的总数。当我们处理新的字符s[i] ch时我们计算add 1 sum(total[prev]) for prev ch。这个add就是由当前这个ch带来的全新序列的数量。然后我们更新total[ch] add。为什么这样能去重因为对于同一个字符ch每次遇到它我们都基于当前时刻所有比它小的字符的总方案数来计算新增量。之前由同一个字符ch产生的序列已经包含在total[prev]的历史累计值中不会在本次计算add时被再次作为“前缀”使用。而add只包含本次新字符产生的新组合。最终整个字符串中所有本质不同的上升子序列总数就是sum(total[c])对所有字符c求和。3.4 算法流程与示例演算让我们用字符串abab来手动演算一下定义total[0..25]对应a到z初始全为0。遍历s[0] a(索引0)比a小的字符没有所以sum_prev 0。add 1 0 1。更新total[a] 1。此时total[a]1其他为0。解释新增了序列a。遍历s[1] b(索引1)比b小的字符有asum_prev total[a] 1。add 1 1 2。更新total[b] 2。此时total[a]1,total[b]2。解释新增了序列b和ab。其中ab是由已有的a后面添加b构成。遍历s[2] a(索引2)比a小的字符没有sum_prev 0。add 1 0 1。更新total[a] 1。此时total[a]2,total[b]2。解释注意这里add是1只新增了序列a吗不对索引2的a和索引0的a形成的序列都是a是同一个本质。所以实际上这次更新没有产生任何新序列。我们的算法哪里出问题了问题暴露我们重复计算了单个字符a。当第二次遇到a时add1代表的新序列a已经存在了。我们的去重逻辑只防止了多字符序列的重复通过依赖total[prev]但没有防止单字符序列的重复。3.5 修正处理单字符重复的最终方案上述演算揭示了我们方案的最后一道障碍如何避免同一个字符形成的单字符子序列被多次计数解决方法其实很简单我们不再将“单字符序列”这个1直接加到add里而是换一种方式初始化。我们可以这样理解所有本质不同的单字符序列就是字符串中出现的不同字符的集合。我们可以在开始动态规划之前就处理好它。修正后的算法流程初始化一个长度为26的数组dp所有元素为0。dp[c]表示以字符c结尾的所有本质不同上升子序列的个数。遍历字符串s的每个字符ch a. 计算增量add 0。 b. 对于所有比ch小的字符prev执行add dp[prev]。这表示当前ch可以接在所有以prev结尾的序列后面形成新序列。 c. 现在add代表了“由当前字符ch与前面更小的字符结尾的序列结合所产生的新序列”的数量。 d. 关键步骤将增量add加到dp[ch]上即dp[ch] add。遍历结束后将所有dp[c]求和得到的结果就是所有长度大于等于2的本质不同上升子序列的数量。最后再加上字符串中不同字符的个数即所有长度为1的本质不同上升子序列。为什么步骤4是加不同字符的个数因为在我们的动态规划过程中dp[ch]的初始值是0。当第一次遇到字符ch时add的计算基于dp[prev]而初始时dp[prev]都是0所以第一次遇到的ch产生的add为0。这意味着我们的dp数组从一开始就没有计入任何单字符序列。单字符序列在“上升”的定义下是平凡的没有前驱字符我们单独计算它们即可。让我们用修正后的算法重新演算abab初始化dp[a]0, dp[b]0。遍历a(索引0)add 0dp[a] 0-dp[a]0。遍历b(索引1)比b小的字符有aadd dp[a] 0dp[b] 0-dp[b]0。遍历a(索引2)add 0dp[a] 0-dp[a]0。遍历b(索引3)比b小的字符有aadd dp[a] 0dp[b] 0-dp[b]0。结束后dp总和为0。字符串中不同字符为{a, b}数量为2。最终结果 0 2 2。验证一下abab的本质不同上升子序列有a,b,ab。等等怎么是3个我们的算法结果2不对ab漏掉了。问题又出在哪里3.6 最终正确的动态规划转移我们离成功只差最后一步了。修正后的算法漏掉了形如ab这样的序列。原因是当我们处理第二个字符b索引1时add的计算依赖于dp[a]而dp[a]在此时仍然是0因为我们第一次遇到a时没有增加任何序列。所以b无法与前面的a结合形成ab。症结在于我们的dp状态应该包含以某个字符结尾的所有序列包括单字符序列。但我们又不想重复计算单字符序列。一个完美的解决方案是在遍历每个字符时我们计算出的add已经包含了由当前字符新构成的所有序列包括接在前驱序列后面的和它自己单独构成的。然后我们用这个add去更新所有大于等于当前字符的dp值吗不这样不对。让我们回归最朴素但正确的思路并用一个例子abc来推导 我们定义dp[i]表示以s[i]结尾的本质不同上升子序列的个数注意这里又回到了以位置结尾但我们会处理重复。当我们计算dp[i]时dp[i] 1 sum(dp[j])其中j i且s[j] s[i]。 这里的1代表子序列s[i]自身。sum(dp[j])代表所有以小于s[i]的字符结尾的序列后面加上s[i]。 但这样会有重复比如aba中两个a结尾的序列会重复。为了去重我们观察到一个重要性质如果当前字符s[i]之前出现过设上一次出现的位置是last那么所有以s[last]结尾的序列都可以被当前这个s[i]重新构造出来这部分是重复的。更准确地说当计算dp[i]时我们应该减去那些已经被前一个相同字符计算过的、以更小字符结尾的序列贡献。因此正确的状态转移方程是 令last[c]记录字符c上一次出现时的dp值即以该位置结尾的序列总数。 当遍历到s[i] ch时计算add 1 sum(dp[j] for j in range(i) if s[j] ch)。这个add是以当前位置i的字符ch结尾的、所有可能的序列数包含新旧。那么本次新增的、不重复的序列数应该是add - last[ch]。因为last[ch]代表了上一次遇到ch时已经计算过的、以ch结尾的序列数这些序列在这次会被重复构造。更新dp[i] add - last[ch]。更新last[ch] add为下一次遇到ch做准备。最终答案就是所有dp[i]的和。对于abab初始化dp数组和last字典记录字符上次的add值初始为0。i0, chaadd 1 0 1。last[a]0。dp[0] 1 - 0 1。last[a] 1。i1, chbadd 1 dp[0] (因为 s[0]a b) 112。last[b]0。dp[1] 2 - 0 2。last[b] 2。新增序列b,abi2, chaadd 1 0 1前面没有比a小的字符。last[a]1。dp[2] 1 - 1 0。last[a] 1。没有新增序列因为单字符a已存在i3, chbadd 1 dp[0] dp[2] (s[0]和s[2]都是a且都小于b) 1 1 0 2。last[b]2。dp[3] 2 - 2 0。last[b] 2。没有新增序列因为b和ab都已存在总和sum(dp) 1 2 0 0 3。符合预期a,b,ab。这个算法的时间复杂度是 O(n * alphabet_size)对于小写字母alphabet_size26所以是 O(26n)效率非常高。空间复杂度为 O(n 26)。4. 代码实现与细节处理理解了上述推导过程代码实现就相对清晰了。以下是用Python实现的示例代码包含了详细的注释def count_distinct_increasing_subsequences(s: str) - int: 计算字符串 s 中本质不同的严格上升子序列的个数。 严格上升指字典序递增。 n len(s) if n 0: return 0 # dp[i] 表示以 s[i] 结尾的本质不同上升子序列的个数本次新增 dp [0] * n # last_add[char] 记录字符 char 上一次出现时计算出的总 add 值。 # 初始化为0表示该字符还未出现过。 last_add [0] * 128 # 使用ASCII码范围简单通用。也可用字典。 for i in range(n): ch s[i] # 1. 计算 add1(自身) 前面所有小于 ch 的字符结尾的序列总数 add 1 for prev_char in range(ord(a), ord(ch)): # 遍历所有比 ch 小的字符 # 注意这里累加的是该字符上一次出现时的总 add 值。 # 这个值代表了截止到上一次出现该字符时以它结尾的所有序列数。 # 这些序列都可以在后面接上当前的 ch。 add last_add[prev_char] # 2. 本次新增的、不重复的序列数 add - 上一次该字符的总序列数 dp[i] add - last_add[ord(ch)] # 3. 更新该字符的最后总序列数记录 last_add[ord(ch)] add # 最终答案是所有 dp[i] 之和 return sum(dp) # 测试用例 if __name__ __main__: print(count_distinct_increasing_subsequences(abab)) # 应输出 3 print(count_distinct_increasing_subsequences(lanqiao)) # 可以测试真题数据代码关键点解析与注意事项last_add数组的含义它存储的是字符c在上一次出现时计算出的add值。这个add值代表的是截止到上一次出现位置以字符c结尾的所有本质不同序列的数量包括单字符c自身。这是去重的核心。内层循环for prev_char in range(ord(a), ord(ch)):这里遍历的是所有ASCII码值小于当前字符ch的字符。我们累加的是这些字符对应的last_add值。为什么是last_add而不是当前时刻以它们结尾的序列总数因为last_add[prev_char]已经包含了截止到该字符最后一次出现时所有以它结尾的序列。之后如果再出现相同的prev_char新产生的序列会更新last_add[prev_char]从而在后续计算中被包含进去。这种设计保证了我们总是基于最新的、完整的“前缀”集合来生成新序列。dp[i]的计算dp[i] add - last_add[ord(ch)]。add是理论上以当前字符ch结尾能形成的所有序列数包括重复的。last_add[ord(ch)]是上一次遇到ch时已经计算过的序列数。两者相减得到的就是本次新出现的、不重复的序列数量。初始化last_add初始为0是合理的表示每个字符在首次出现前其历史序列数为0。字符范围代码中使用了last_add[128]覆盖了ASCII码的基本范围。如果题目明确只有小写字母可以优化为last_add[26]通过ord(ch) - ord(a)来索引效率更高。大数处理蓝桥杯真题的字符串可能很长结果可能非常大需要关注题目要求的数据类型。在Python中整数可以自动处理大数但在C/Java中可能需要使用long long或高精度计算。5. 常见错误与调试心得在理解和实现这道题的过程中我以及我见过的很多同学都容易踩进以下几个坑坑1混淆“位置”和“字符”维度最初总想着用dp[i]直接表示以位置i结尾的总数然后求和。这必然导致重复计数因为不同位置可能产生相同的序列。必须意识到去重需要我们将状态从“位置”聚合到“字符”层面或者像最终解法一样在“位置”维度上进行精细的重复项减除。坑2忽略单字符序列的去重这是最隐蔽的坑。当我们用“增量更新”的思路时很容易忘记单字符序列a在字符串中出现多次时只应被计算一次。我们的最终解法通过dp[i] add - last_add[ch]巧妙地处理了这个问题因为对于第一次出现的字符last_add[ch]0dp[i]add包含了1它自身对于第二次出现的相同字符上次的add包含了1被减去从而抵消了新增的单字符序列。坑3错误理解last_add的更新时机last_add[ch]必须在计算完本次的dp[i]后才更新为新的add值。如果先更新last_add再计算dp[i]就会导致dp[i] add - add 0完全错误。顺序是计算add- 计算dp[i]- 更新last_add[ch] add。坑4内层循环累加对象错误在内层循环累加“前缀”序列数时是累加last_add[prev_char]而不是dp[某个位置]。因为last_add[prev_char]代表了以字符prev_char结尾的所有历史序列总和这正是当前字符ch可以接在后面形成新序列的“基础数量”。调试建议从小例子开始像a,aa,ab,aba,abab这样的短字符串手工计算出所有本质不同上升子序列然后单步调试你的程序观察dp和last_add数组的变化是否与你的手动推导一致。打印中间变量在循环中打印i,ch,add,dp[i],last_add[ord(ch)]的值对于理解数据流非常有帮助。对比两种理解将“以位置结尾”和“以字符结尾”两种动态规划思路的中间结果都打印出来对比它们的差异能深刻理解去重的本质。6. 算法扩展与相关真题链接掌握了“本质上升序列”的解法其实就掌握了一类“带去重的子序列计数”问题的核心思想。这个思想可以扩展到更多场景修改上升规则如果不是严格字典序递增而是非递减即允许相等状态转移中的比较条件s[j] s[i]就需要改为s[j] s[i]同时去重逻辑要更加小心因为相同字符连续出现时序列aa也应该被允许。计数模一个大数蓝桥杯题目经常要求结果对1e97取模。我们只需要在每次加法运算add last_add[prev_char]和dp[i] add - last_add[ch]后加上取模操作即可。注意减法后可能得到负数需要(add - last MOD) % MOD来调整。与最长上升子序列LIS问题的关系这是动态规划的经典入门题。LIS求的是最大长度通常用dp[i]表示以i结尾的LIS长度用二分查找优化可以达到 O(n log n)。而本题求的是去重后的序列总数维度不同优化思路也不同。将两者对比学习能更好地理解DP状态设计如何影响问题复杂度。在蓝桥杯真题库中与此题思想相关的题目还有“不同的子序列”给定一个字符串s和一个字符串t计算在s的子序列中t出现的个数。这也是一个经典的动态规划计数问题状态通常定义为dp[i][j]表示s的前i个字符中t的前j个字符出现的次数。其转移方程也涉及去重思想当s[i-1] t[j-1]时可以选择匹配或不匹配。“上升子序列和”求所有上升子序列的最大和。这又是一种变体状态dp[i]表示以i结尾的上升子序列的最大和转移方程为dp[i] max(dp[i], dp[j] s[i])当s[j] s[i]。这道“本质上升序列”题就像一把钥匙打开了用动态规划解决复杂计数问题的大门。它告诉我们面对计数问题尤其是涉及“本质不同”的去重时单纯枚举然后去重是行不通的必须在状态转移的过程中就嵌入去重的逻辑。而实现这一点的关键往往在于寻找一个恰当的状态定义以及维护额外的信息如last_add来记录历史从而在计算增量时能够精确地剔除重复部分。在平时练习时不妨多找几道类似的计数DP题目反复体会这种“在过程中去重”的思想这对于提升竞赛水平和解决实际编程问题都大有裨益。