动态规划解决本质不同上升子序列计数问题

1. 问题引入从“本质上升序列”说起最近在整理蓝桥杯国赛的历年真题发现“本质上升序列”这道题出现的频率不低而且常常作为动态规划DP的经典例题。很多同学第一次看到这个名词可能会有点懵上升序列好理解那“本质”又是什么意思这其实是一个在字符串处理中非常精妙的概念它考察的不仅仅是基础的递推能力更是对“状态定义”和“去重逻辑”的深刻理解。简单来说给定一个字符串我们要找出所有不同的、严格递增的子序列。这里的“不同”不是指序列内容不同而是指作为子序列它们在原字符串中的出现方式是唯一的。举个例子字符串 “abc”它的本质上升序列有 “a”, “b”, “c”, “ab”, “ac”, “bc”, “abc” 共7个。但如果字符串是 “aba” 呢“a” 这个字符出现了两次以第一个‘a’开头的序列和以第二个‘a’开头的序列如果内容相同算作同一个“本质”序列吗这就是问题的关键和难点所在。我最初做这类题时很容易掉进一个陷阱直接用求所有子序列数量的思路然后试图去重结果发现情况复杂代码冗长且容易出错。后来经过反复琢磨和参考一些优秀的解法才领悟到动态规划在这里的巧妙应用——它通过一种“贡献计数”和“容斥”的思想优雅地解决了去重问题。今天我就把自己对这道题的理解、完整的动态规划推导过程、关键的代码实现细节以及一些容易踩的坑系统地梳理一遍。无论你是正在备赛蓝桥杯还是单纯想提升动态规划的解题能力相信这篇内容都能给你带来实实在在的收获。2. 核心概念拆解什么是“本质”不同的上升子序列在深入动态规划之前我们必须把“本质上升序列”这个定义掰开揉碎了理解。这直接决定了我们状态转移方程的正确性。2.1 子序列 vs. 子串这是一个基础但重要的区分。子串要求字符必须是连续的比如 “abcde” 中“bcd” 是一个子串。而子序列只要求字符顺序保持不变可以不连续比如 “ace” 就是 “abcde” 的一个子序列。我们的问题针对的是子序列。2.2 “上升”的含义在这个语境下“上升”指的是子序列中字符的ASCII码值严格递增。对于纯小写字母字符串就是字母在字母表中的顺序严格递增‘a’ ‘b’ ‘c’ …。这意味着序列中不能有重复字符且顺序必须递增。2.3 “本质不同”的精髓与难点这是本题的核心。本质不同不是指序列的字符串内容不同而是指这个序列作为原字符串的一个子序列其选取字符的下标组合是唯一的。换句话说即使两个子序列的内容一模一样只要它们是由原字符串中不同位置的字符组成的我们就认为它们是“不同”的。但是在“本质不同”的定义下它们被视为同一个。让我们用 “ababc” 这个字符串来举例说明内容为 “ab” 的子序列有哪些选取第1个’a’下标0和第2个’b’下标1 - 得到 “ab”选取第1个’a’下标0和第4个’b’下标3 - 得到 “ab”选取第3个’a’下标2和第4个’b’下标3 - 得到 “ab” 这里我们得到了三个内容同为 “ab” 的子序列但它们来自原串不同的位置组合。在传统的“所有不同子序列”计数问题中上述三个都会被计入。但在“本质上升序列”问题中它们被视为同一个本质序列。因为当我们说“本质”时我们只关心序列的字符串内容而不关心这个内容是由原串中哪几个具体位置的字符拼凑出来的。所以问题的目标转化为统计原字符串中所有由不同字符组成的、严格递增的、内容互不相同的子序列的个数。空序列通常不计入。2.4 问题转化与动态规划可行性分析现在我们的目标清晰了统计所有内容不同的严格递增子序列。暴力枚举所有子序列再对内容去重时间复杂度是 O(2^n)对于蓝桥杯的典型数据规模字符串长度可达200是完全不可行的。动态规划的思路在于“递推”和“状态记录”。我们能否定义一种状态dp[i]来表示以某个字符或某个位置结尾的某种数量然后通过状态转移来累计总数同时自动规避重复内容的计数一个直接的启发是既然我们只关心序列的内容那么对于以相同字符结尾、且内容相同的序列我们只应计数一次。例如所有以 ‘b’ 结尾的、内容为 “ab” 的序列我们只算一个。这提示我们状态可能需要和字符本身而不仅仅是位置相关联。更进一步为了满足“上升”特性当我们考虑一个序列结尾加上一个新字符时这个新字符必须大于序列原有的最后一个字符。这就引出了本题最经典的一种DP定义方式dp[c]表示以字符c结尾的、所有本质不同的严格递增子序列的个数。这里c是一个具体的字符如 ‘a’ ‘b’。3. 动态规划状态定义与转移方程推导基于上一节的分析我们采用以字符为维度的DP。假设字符串s的长度为n字符集为小写字母26个。3.1 状态定义定义dp[26]数组dp[c]表示遍历字符串到当前位置时以字符c结尾的、所有本质不同的严格递增子序列的数量。 这里c是字符的索引例如dp[0]对应字符 ‘a’dp[1]对应 ‘b’以此类推。3.2 状态初始化初始时没有任何字符被考虑所有dp[c] 0。3.3 状态转移方程核心我们顺序遍历字符串s的每一个字符s[i]。设当前字符为ch其对应的索引为idx ch - ‘a’。当我们遇到ch时它可以作为一个全新的、长度为1的子序列即序列”ch”。这是一个以ch结尾的本质序列。接在某个已有的、结尾字符比它小的子序列后面形成一个新的、更长的、以ch结尾的子序列。关键点在于如何计算新增的数量并且保证“本质不同”对于情况1新增的数量就是1序列”ch”本身。对于情况2假设存在一个以字符x结尾的序列xch那么这个序列后面加上ch就形成了一个新的以ch结尾的序列。这个新序列的内容等于原序列内容拼接上ch。由于原序列是本质不同的且拼接操作是确定的所以这些新序列在内容上也是互不相同的。那么有多少个这样的“原序列”呢就是所有以小于ch的字符结尾的序列数量之和。即sum(dp[0] dp[1] … dp[idx-1])。因此当遍历到字符ch时以ch结尾的本质序列总数dp[idx]的增量就是1 sum(dp[0…idx-1])。但是这里有一个极其重要的细节我们不能简单地将这个增量加到dp[idx]上。考虑字符串 “ababc”再次关注字符 ‘b’第一次遇到 ‘b’下标1时dp[‘b’]更新为1 dp[‘a’]。假设此时dp[‘a’]1序列”a”那么dp[‘b’] 1 1 2。这两个序列分别是”b” 和 “ab”。第二次遇到 ‘b’下标3时如果我们还用同样的公式1 sum(dp[‘b’])来计算增量并累加那么sum(dp[‘b’])此时包含了第一次遇到 ‘b’ 时产生的序列 “ab”。增量就是1 dp[‘a’]假设dp[‘a’]还是1增量又是2。那么dp[‘b’]就会变成2 2 4。 这4个序列被认为是第一次 ‘b’ 产生的 “b”, “ab”第二次 ‘b’ 产生的 “b”, “ab”。看内容为 “ab” 的序列被计算了两次这违反了“本质不同”的原则。问题的根源在于当同一个字符ch重复出现时以它结尾的、内容相同的序列会被重复计算。例如内容为 “ab” 的序列无论是用第一个 ‘b’ 还是第二个 ‘b’ 作为结尾其内容是一样的。我们的DP状态dp[‘b’]应该只记录内容不同的序列所以第二次遇到 ‘b’ 时我们不能把那些“用第一个 ‘b’ 已经能形成的、相同内容的序列”再算进去。正确的做法是在更新dp[idx]之前先将其重置为0。为什么dp[idx]记录的是“以字符ch结尾”的本质序列。当我们遇到一个新的ch比如第二个 ‘b’时之前dp[idx]里记录的所有序列其结尾的ch是上一次出现的那个 ‘b’。现在我们有新的 ‘b’ 可用所有以这个新 ‘b’ 结尾的序列其构成方式即前面拼接哪些小于 ‘b’ 的字符序列和以前是一样的。但是如果直接累加就会把“相同内容、不同结尾位置”的序列重复计数。更准确的理解是对于字符ch在任何时刻dp[idx]应该只记录由“最近一次出现的ch”所能形成的、以ch结尾的本质序列数量。因为对于更早出现的ch它所能形成的序列其内容都可以由最近出现的这个ch来“代表”形成。所以当我们遇到一个新的ch时我们应该用这个新ch重新计算dp[idx]覆盖掉旧值。因此完整的状态转移过程如下 遍历字符串s的每个字符ch(索引idx)计算total 1 sum(dp[0] dp[1] … dp[idx-1])。这个total代表由当前这个ch所能新形成的、以ch结尾的本质序列数量包括它自己 “ch”。将dp[idx]更新为total。注意是更新赋值不是累加。3.4 最终答案遍历完整个字符串后我们需要的是所有本质不同的严格递增子序列的数量。这包括了以 ‘a’, ‘b’, …, ‘z’ 所有字符结尾的序列。因此最终答案就是sum(dp[0] dp[1] … dp[25])。让我们用 “ababc” 来手动模拟验证一下 初始化dp[a..b]0遇到 ‘a’ (idx0):total 1 sum(dp[‘a’]) 1 0 1。dp[0] 1。 (序列: “a”)遇到 ‘b’ (idx1):total 1 sum(dp[0]) 1 1 2。dp[1] 2。 (序列: “b”, “ab”)遇到 ‘a’ (idx0):total 1 sum(dp[‘a’]) 1 0 1。dp[0] 1。 (覆盖序列仍为 “a”。注意虽然’a’出现了两次但以’a’结尾的序列只有内容为”a”的这一种)遇到 ‘b’ (idx1):total 1 sum(dp[0]) 1 1 2。dp[1] 2。 (覆盖序列为 “b”, “ab”。这里“ab”可以由(第一次的’a’第二次的’b’)或(第二次的’a’第二次的’b’)形成但内容相同只算一次)遇到 ‘c’ (idx2):total 1 sum(dp[0]dp[1]) 1 (12) 4。dp[2] 4。(序列: “c”, “ac”, “bc”, “abc”) 最终sum(dp) dp[0]dp[1]dp[2] 1 2 4 7。 我们枚举一下所有本质序列”a”, “b”, “c”, “ab”, “ac”, “bc”, “abc”。正好7个。符合预期。4. 算法实现、优化与代码详解理解了状态转移方程代码实现就相对直观了。但其中仍有几个细节需要敲定否则容易出错。4.1 基础版本代码实现Pythondef count_distinct_increasing_subsequences(s: str) - int: 计算字符串 s 中本质不同的严格递增子序列个数。 假设 s 仅由小写字母组成。 MOD 10**9 7 # 蓝桥杯常见要求结果取模 dp [0] * 26 # dp[i] 表示以字符 (ai) 结尾的本质序列数 for ch in s: idx ord(ch) - ord(a) # 计算所有小于当前字符的序列数之和 total 1 # 当前字符自身作为一个序列 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 # 测试 print(count_distinct_increasing_subsequences(abc)) # 输出7 print(count_distinct_increasing_subsequences(ababc)) # 输出7代码关键点解读字符索引转换ord(ch) - ord(‘a’)将小写字母映射到 0-25。内层循环求和for i in range(idx):累加了所有小于ch的字符对应的dp[i]即sum(dp[0…idx-1])。直接赋值dp[idx] total是保证“本质不同”的核心操作。它确保了dp[idx]始终记录的是由当前最后出现的字符ch所能形成的序列数。取模操作蓝桥杯题目通常要求对一个大数取模防止结果溢出。我们在加法和最终求和时都需要取模。4.2 时间复杂度优化前缀和基础版本的时间复杂度是 O(26 * n)对于长度 n 很大、但字符集固定为26的小写字母来说已经是 O(n) 级别完全足够。但内层循环的for i in range(idx)毕竟是一个常数但也不小的开销最多26次。我们可以引入一个前缀和数组prefix_sum来优化。prefix_sum[i]表示当前状态下dp[0] dp[1] … dp[i]的和。这样计算sum(dp[0…idx-1])就可以在 O(1) 时间内完成。优化后代码如下def count_distinct_increasing_subsequences_opt(s: str) - int: MOD 10**9 7 dp [0] * 26 # 前缀和数组 prefix[i] 表示 dp[0]...dp[i] 的累加和 prefix [0] * 26 for ch in s: idx ord(ch) - ord(a) # 计算 sum(dp[0...idx-1]) 即 idx0 时的 prefix[idx-1]否则为0 prev_sum prefix[idx-1] if idx 0 else 0 total (1 prev_sum) % MOD dp[idx] total # 更新前缀和数组 # 从 idx 开始后面的前缀和都需要加上 dp[idx] 的变化量 (total - old_val) # 但我们之前是直接赋值所以变化量就是 total (因为 old_val 被覆盖了等价于增加了 total) # 更稳妥的方式是重新计算 prefix # 由于字符集只有26这里选择重新计算 prefix 也是 O(26)清晰不易错 prefix[0] dp[0] % MOD for i in range(1, 26): prefix[i] (prefix[i-1] dp[i]) % MOD return prefix[25] # 即 sum(dp[0..25]) # 测试 print(count_distinct_increasing_subsequences_opt(ababc)) # 输出7这个优化在理论复杂度上没变但常数更小。在竞赛中基础版本通常就够用了但掌握前缀和的思想是很好的。4.3 处理更一般字符集的情况如果题目没有说明字符集或者字符串包含大写字母、数字等我们的DP数组大小就不能固定为26了。一种通用的方法是使用字典HashMap来动态维护以每个字符结尾的序列数量。但转移时我们需要求所有“小于当前字符ch的键对应的值”之和。这需要对字典的键进行排序或遍历复杂度会上升到 O(k * n)其中 k 是当前已出现的不重复字符数。在字符集很大时如Unicode这种方法可能效率较低。不过蓝桥杯的此类题目通常明确字符范围为小写字母。5. 典型错误分析与避坑指南这道题思路清晰后代码不长但几乎每个点都可能成为陷阱。下面是我在练习和教学中总结的几个常见错误5.1 错误1对dp[idx]进行累加而非赋值这是最经典、最隐蔽的错误。错误代码示例# 错误代码 for ch in s: idx ord(ch) - ord(a) total 1 for i in range(idx): total dp[i] dp[idx] total # 致命错误这里用了 这种写法的结果会远大于正确答案因为它重复计数了所有由之前出现的相同字符所形成的、内容相同的序列。一定要记住dp[idx] total。5.2 错误2初始化dp数组时包含了空序列有些同学可能会想空序列””是不是也应该算一个本质序列通常题目要求统计的是非空上升子序列。我们的算法中total 1代表的就是当前字符自身形成的长度为1的序列。如果我们把空序列也算上初始化时dp全为1或者在求和时额外加1这完全取决于题意。蓝桥杯真题中通常要求的是非空序列。所以务必仔细审题。我们的算法默认统计非空序列。5.3 错误3忽略“严格递增”条件允许了相等字符在状态转移时我们只累加dp[i]其中i idx这保证了严格递增s[i]s[idx]。如果题目变成“非递减”那么条件就要改为i idx但同时“本质不同”的定义可能也需要调整因为连续相同字符会产生大量内容相同但下标不同的序列去重逻辑会变得更复杂。这类变形题需要重新分析。5.4 错误4取模运算的位置不当在竞赛中结果往往很大需要取模。常见的错误是只在最后求和时取模而在中间计算total时没有取模可能导致中间结果溢出在Python中虽然整数不限大小但效率会受影响且不符合常规的取模运算流程。正确的做法是在每一次加法运算后立即取模。total 1 for i in range(idx): total (total dp[i]) % MOD # 每次加法都取模 dp[idx] total # total 已经取过模5.5 错误5对“本质不同”理解偏差试图用集合去重这是初学者最容易走的弯路。他们会先求出所有可能的子序列2^n 量级然后将其放入一个集合set中去重最后再筛选出上升的序列。且不论时间复杂度爆炸光是生成所有子序列就已经不可行了n30时2^30 10亿。动态规划的魅力就在于它通过巧妙的状态定义在计算过程中就天然地避免了重复计数无需事后去重。理解这一点是掌握此类DP问题的关键。6. 实战演练与变种思考为了加深理解我们来看一道具体的蓝桥杯国赛真题题目描述已做简化例题对于一个字符串定义它的“价值”为其所有本质不同的严格递增子序列的个数。例如”abc” 的价值是7。现在给定一个长度为 n (1 ≤ n ≤ 200) 的、仅包含小写字母的字符串请你计算它的价值。结果对 10^97 取模。这就是我们上面讨论的“标准题型”。直接用我们推导出的算法即可解决。变种思考1统计长度至少为L的本质上升序列个数如果题目问的不是所有序列而是长度至少为 L 的序列个数该如何修改 思路我们的dp[c]现在不能只记录数量了需要记录以字符c结尾的、长度为len的序列有多少个。我们可以定义一个二维数组dp[len][c]其中len表示序列长度。状态转移时dp[len][idx] sum(dp[len-1][i] for i in range(idx))。同时每个字符自身形成长度为1的序列dp[1][idx] 1。最终答案是所有len L的dp[len][c]之和。这实际上是一个基于字符和长度的二维DP。变种思考2枚举具体序列内容如果题目要求输出所有本质不同的上升子序列而不仅仅是计数怎么办 动态规划通常用于计数枚举所有序列需要回溯。我们可以用dp[c]存储一个集合set集合里是以字符c结尾的所有本质序列的字符串本身。状态转移时新的集合是{ch}与{seq ch for seq in dp[i] for i in range(idx)}的并集。但这样空间和时间开销极大仅适用于非常短的字符串n20。这提醒我们DP计数和枚举具体解往往是不同难度的问题。变种思考3字符集扩大如果字符串包含数字和大写字母我们可以将dp数组大小扩大到62102626或者使用字典。计算sum(dp[ch])时需要对所有键小于当前字符ch的项求和。如果字符集是全ASCII甚至Unicode这种方法的效率会变低可能需要借助数据结构如树状数组来维护前缀和将复杂度优化到 O(n log C)其中C是字符集大小。通过解决“本质上升序列”这个经典问题我们深入练习了动态规划中如何通过精巧的状态定义来处理“去重”这一难题。其核心思想——用当前最后出现的某个字符来“代表”所有以该字符结尾的相同内容序列——非常具有启发性可以推广到其他需要处理“本质不同”子序列的题目中去。在竞赛中看到“本质不同”、“不同子序列”等关键词并且序列有顺序要求递增、递减、特定模式时就要联想到这种以结尾元素定义状态并通过覆盖更新来去重的DP模型。多练习多思考状态转移的物理意义是掌握动态规划的不二法门。