1. 项目概述从一道经典竞赛题说起最近在整理历年算法竞赛的经典题目时我又翻出了2020年第十一届蓝桥杯决赛JAVA B组的D题——“本质上升子序列”。这道题在当时的赛场上给不少选手带来了不小的挑战它看似是动态规划中“最长上升子序列”问题的变种但“本质不同”这个约束条件一下子把问题的复杂度提升了一个维度。很多朋友在初次接触时容易陷入重复计数的陷阱或者写出时间复杂度爆炸的暴力解法。今天我就以一个过来人的身份和大家一起彻底拆解这道题。我们不仅会探讨如何用动态规划高效求解更会深入分析“本质不同”的含义并对比多种解法的优劣最后分享一些在竞赛中快速识别和解决此类问题的实战技巧。无论你是正在备赛蓝桥杯的学生还是对算法感兴趣的开发者相信这篇深度解析都能让你对子序列类问题有更透彻的理解。2. 问题核心理解“本质上升子序列”在动手写代码之前我们必须把题目要求吃透。很多失误都源于对问题定义的模糊理解。2.1 题目定义与关键约束题目通常会给一个字符串s由小写字母组成要求我们找出其所有“本质不同的上升子序列”的个数并对结果取模。这里我们需要明确三个关键概念子序列由原字符串在不改变字符相对顺序的情况下删除某些字符也可以不删除得到的新序列。例如对于字符串“abc”“a”、“ac”、“b”都是它的子序列而“ca”不是。上升子序列对于字符串通常将字符的ASCII码值或字典序作为“大小”依据。一个子序列是“上升”的当且仅当它的每个字符都比前一个字符大严格递增。例如在“abc”中“ac”是上升的a c而“ba”不是。本质不同这是本题的核心难点。它指的是两个子序列的内容即字符序列本身不同。例如字符串“aba”中考虑以第一个‘a‘结尾和以第二个‘a‘结尾的、内容为“a“的子序列。虽然它们来自原字符串的不同位置但内容都是“a“因此它们被视为同一个本质子序列在计数时只算一次。注意本质不同与子序列的“来源位置”无关只与最终构成的字符序列有关。这是最容易混淆的地方。许多初学者会试图记录子序列的结尾索引来区分但这对于“本质不同”的判断是无效的。2.2 与经典LIS问题的本质区别最长上升子序列LIS问题是动态规划的入门经典。其标准动态规划定义dp[i]表示以第i个元素结尾的最长上升子序列长度状态转移方程为dp[i] max(dp[j]) 1 (其中 j i 且 nums[j] nums[i])。LIS问题关心的是“长度”的最大值。而本题“本质上升子序列个数”问题关心的是“数量”的累加。更重要的是LIS问题在计数时如果原序列有重复值以不同位置的相同值结尾的、长度相同的LIS会被视为不同的序列吗这取决于具体问法。但本题明确要求“本质不同”因此我们必须从状态定义上就杜绝重复内容的产生。这引导我们不能再简单地以“以某个位置结尾”来定义状态因为相同内容可能由不同位置产生。3. 动态规划思路深度拆解面对计数问题尤其是带“去重”要求的动态规划往往是首选。我们需要设计一个能规避重复计数的状态表示。3.1 状态定义的艺术既然“以位置i结尾”会导致重复我们尝试升维从字符本身入手。定义dp[i]表示以字符i这里i代表某个特定字符例如‘a‘‘b‘…结尾的、本质不同的上升子序列的个数。这个定义的精妙之处在于它将所有以相同字符结尾的子序列无论它们在原字符串中来自哪个位置都归并到了同一个状态里。这天然地解决了“本质不同”的去重要求。例如字符串“aba“中所有以‘a‘结尾的本质不同上升子序列其数量就存储在dp[‘a‘]中。3.2 状态转移方程的推导我们如何计算dp[i]呢假设当前遍历到原字符串中的字符ch。新建子序列字符ch本身可以作为一个长度为1的上升子序列。因此我们需要为dp[ch]增加1。接续已有子序列对于所有比ch小的字符smallChar即满足smallChar ch以smallChar结尾的任何本质不同上升子序列在其末尾添加上当前字符ch都能形成一个新的、以ch结尾的上升子序列。并且由于dp[smallChar]已经代表了所有以smallChar结尾的本质不同序列这些新序列也一定是本质不同的。去重关键这里会出现重复吗考虑字符串“abab“。当处理第二个‘b‘时它会尝试接在以‘a‘结尾的序列后面。而以‘a‘结尾的序列集合是固定的{“a“}。无论是第一个‘b‘还是第二个‘b‘接上后产生的新序列内容都是“ab“。如果我们简单地累加“ab“会被计算两次。但我们的状态dp[‘b‘]是以字符‘b‘结尾的序列个数。第一个‘b‘处理完后dp[‘b‘]已经包含了“b“和“ab“。当处理第二个‘b‘时我们如果再次将dp[‘a‘]的值加到dp[‘b‘]上就会导致“ab“被重复计算。因此正确的做法不是每次遇到字符都无脑累加。我们需要确保对于同一个字符ch在它多次出现时后续出现的位置不应该重复计算那些“由更早出现的相同字符ch已经计算过的”接续方案。解决方案是在遍历每个字符时我们计算的是“以本次出现的这个字符ch为结尾能新增多少本质不同的子序列”。然后用这个“新增量”去更新全局的dp[ch]。更具体地说我们可以用一个临时变量add来表示本次新增的数量。状态转移方程如下 假设当前遍历到字符ch。令add 1。这代表字符ch自身作为一个新序列。遍历所有字符c从‘a‘到比ch小的字符执行add dp[c]。这代表将所有以较小字符结尾的序列后接ch形成的新序列。那么add就代表了由当前这个位置的ch字符所带来的、全新的、以ch结尾的本质不同子序列的数量。最后将add累加到dp[ch]上dp[ch] add。这个过程中add的计算依赖于当前时刻的dp值即处理当前字符之前的状态。这保证了对于后面再次出现的相同字符ch‘它计算add时所基于的dp数组已经包含了之前字符ch所贡献的所有序列因此ch‘计算出的add不会包含重复项。3.3 初始化与最终结果初始化非常简单将所有字符对应的dp值设为0。 最终整个字符串遍历完成后我们需要的答案是所有可能的结尾字符所对应的序列数之和即sum(dp[‘a‘] 到 dp[‘z‘])。因为题目要求所有上升子序列无论以什么字符结尾都需要统计。实操心得在竞赛中为了编码方便我们通常会将字符映射到数组下标。例如dp[0]对应‘a‘dp[25]对应‘z‘。这样可以用循环轻松处理。另外由于结果可能很大题目通常会要求对一个大质数如1e97取模每一步加法运算后都要记得取模防止溢出。4. 算法实现与代码详解理论清晰后我们来看具体的代码实现。这里提供Java版本的核心代码并附上详细注释。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); String s sc.next(); int MOD 1000000007; // dp数组dp[i]表示以字符(‘a‘i)结尾的本质不同上升子序列个数 long[] dp new long[26]; // 遍历原字符串的每一个字符 for (int i 0; i s.length(); i) { int cur s.charAt(i) - ‘a‘; // 当前字符对应的索引 long add 1; // 新增数量初始为1代表当前字符自身作为一个序列 // 累加所有比当前字符小的字符结尾的序列数 for (int j 0; j cur; j) { add (add dp[j]) % MOD; } // 将本次新增的数量加到以当前字符结尾的总数上 dp[cur] (dp[cur] add) % MOD; } // 计算最终答案所有字符结尾的序列数之和 long ans 0; for (long num : dp) { ans (ans num) % MOD; } System.out.println(ans); sc.close(); } }代码逐行解析long[] dp new long[26];使用long类型防止中间结果溢出。数组下标0-25分别对应字符‘a‘到‘z‘。主循环for (int i 0; i s.length(); i)依次处理字符串中的每个字符。int cur s.charAt(i) - ‘a‘;将当前字符转换为0-25的索引。long add 1;add变量至关重要它代表由当前这个位置的字符新贡献的、以该字符结尾的序列数。初始值1代表该字符本身。内层循环for (int j 0; j cur; j)遍历所有比当前字符小的字符。dp[j]中存储了在遇到当前字符之前所有以字符j结尾的本质不同序列。这些序列后面加上当前字符都能形成新的、以当前字符结尾的序列且不会与之前产生的序列重复因为结尾字符不同或者序列内容因当前字符位置不同而本质不同。将这些数量累加到add中。dp[cur] (dp[cur] add) % MOD;将本次计算得到的add值累加到dp[cur]中。这一步更新了以cur字符结尾的总序列数。这正是去重的核心如果同一个字符在后面再次出现它计算add时使用的是更新前的dp数组因此不会重复计算之前已经生成过的、以该字符结尾的序列。最后遍历dp数组求和即为所有本质不同上升子序列的总数。时间复杂度分析外层循环遍历字符串长度为n内层循环固定为最多26次字符集大小。因此总时间复杂度为O(26 * n)对于n高达10^5的数据范围也完全可行。空间复杂度仅使用了一个大小为26的dp数组为O(1)。5. 对比分析与思路演进理解一种解法后再看看其他思路为何行不通或效率低下能加深我们对问题本质的理解。5.1 暴力枚举法及其局限性最直接的思路是枚举所有可能的子序列判断其是否上升且本质不同。枚举子序列的时间复杂度是O(2^n)n为字符串长度这显然是不可接受的。即使使用哈希集合如HashSet来自动去重枚举的指数级复杂度也无法处理稍大的数据n 30就非常困难。竞赛题的数据范围通常设计为迫使选手寻找更优算法。5.2 基于位置定义的动态规划为何失败如果我们定义dp[i]为以字符串中第i个位置字符结尾的本质不同上升子序列个数。状态转移时我们需要找到所有j i且s[j] s[i]的位置将dp[j]累加到dp[i]。但这里有一个致命问题不同的j1和j2位置如果s[j1] s[j2]那么以它们结尾的序列集合可能存在大量重复内容。例如“aba“以第一个‘a‘结尾的序列有{“a“}以第二个‘a‘结尾的序列也有{“a“}。在计算以‘b‘结尾的序列时dp[‘b‘]会分别加上dp[第一个‘a‘]和dp[第二个‘a‘]导致序列“ab“被计算两次。要基于位置dp去重需要在状态转移时进行复杂的判重通常需要用到集合导致时间复杂度劣化。5.3 基于字符定义的动态规划的优势我们采用的解法基于字符的dp之所以高效是因为它进行了状态压缩。它将原本可能分散在多个不同位置、但结尾字符相同的状态压缩成了一个状态。这个状态天然地代表了“所有以该字符结尾的本质不同序列”这个集合的总数。转移时我们不再关心这个序列来自原字符串的哪个具体位置只关心它的结尾字符和数量。这完美契合了“本质不同”的要求同时将内层循环的复杂度从O(n)降到了O(26)。6. 常见错误与调试技巧在实际编码和调试过程中我总结了一些常见的“坑点”。6.1 整数溢出问题这是竞赛中最常见的失分点之一。即使最终答案在取模后可能不大但中间累加过程(add dp[j])可能会超过int型的最大值约21亿。题目数据往往就是为此设计的。避坑技巧在Java中对于这类计数问题无脑使用long类型来定义dp数组和中间变量。并且在每一次加法运算后立即取模养成习惯。6.2 去重逻辑混淆有些同学理解了一半知道要用一个“总的”dp[char]但在更新时写成了dp[cur] add;而不是dp[cur] add;。这错误地将当前字符本次出现所产生的新序列完全覆盖了之前产生的所有序列。例如处理“ab“时遇到‘b‘add计算为1 dp[‘a‘] 2序列“b“和“ab“。如果使用覆盖赋值dp[‘b‘]最终为2这看似正确。但遇到“aba“处理最后一个‘a‘时add为1因为此时dp[‘b‘]是2但‘b‘不比‘a‘小所以不累加。如果覆盖赋值dp[‘a‘]最终为1但正确答案应该是2序列“a“第一个位置和“a“第三个位置本质相同只算一个序列“aba“不是上升的因为b a不满足。实际上dp[‘a‘]应该在第一个‘a‘时就已被更新为1遇到第三个‘a‘时add为1累加后dp[‘a‘]变为2代表以‘a‘结尾的序列有“a“和“?a“其中 ? 是小于a的字符这里没有所以就是“a“本身。这个例子恰好结果也是2但逻辑是错误的。正确的累加逻辑才能应对所有情况。6.3 模运算的细节取模运算(a b) % MOD在Java中没问题但如果你需要计算(a - b) % MOD且保证结果非负应该写成(a - b MOD) % MOD。虽然本题只有加法但这是一个重要的技巧。另外确保你的MOD值是int类型但参与运算的变量是long以防止乘法运算溢出。6.4 测试用例设计自己设计测试用例是调试的利器。可以从简单到复杂边界用例空字符串““如果题目允许答案应为0。单字符字符串“a“答案应为1只有“a“本身。无重复字符“abc“所有上升子序列为“a“,“b“,“c“,“ab“,“ac“,“bc“,“abc“共7个。可以用程序验证。有重复字符“aba“本质不同的上升子序列有“a“,“b“,“ab“。注意“ba“不是上升的b a? 不b a 是上升的但这里 b在a后面序列”ba”的顺序是原串中b(位置2)和a(位置3)23且‘b‘‘a‘满足上升等等仔细看字符串 “a b a“索引1 2 3。子序列”ba“取自索引2的b和索引3的ab a 不满足严格递增所以不是上升序列。。“aa“也不是上升的a 不大于 a。所以答案是3。复杂用例“abab“。可以手工推导或编写一个暴力枚举程序用于小数据来验证动态规划程序的结果。7. 竞赛实战策略与扩展思考在时间紧张的竞赛环境中如何快速解决此类问题7.1 快速识别模型看到“子序列”、“计数”、“本质不同”这些关键词就要立刻想到动态规划。如果还有“上升”递增条件那么状态定义很可能会与“结尾元素”相关。当发现重复元素可能导致重复计数时应果断放弃以“索引位置”结尾的定义尝试升维或改变状态定义例如用“以某个值结尾”来替代“以某个位置结尾”。这种“以值代位”的思路在去重计数问题中非常常见。7.2 模板化与编码速度对于这种字符集固定的问题26个小写字母可以准备一个模板dp数组长度26。双循环外层遍历字符串内层遍历比当前字符小的所有字符进行累加。使用long类型和即时取模。熟练后5分钟内完成编码和基本测试是可行的。7.3 问题变种与扩展字符集扩大如果不是小写字母而是0-9的数字或者ASCII码范围解法完全一样只需调整dp数组大小。下降子序列将内层循环条件从j cur改为j cur即可。非严格上升不下降将内层循环条件从j cur改为j cur。但要注意这可能会引入新的重复计数问题需要结合“本质不同”的定义仔细分析。通常对于非严格上升且本质不同需要在状态转移时只考虑最后一次出现的位置这需要额外的数组来记录每个字符上一次出现时的add值并在本次更新时减去上一次的贡献以避免同一内容序列因中间插入相同值而被重复计算。这比严格上升的情况要复杂一些。求具体方案如果题目要求输出所有本质不同的上升子序列而不仅仅是计数那么动态规划就需要记录路径。这通常需要用到集合或字典树来存储序列本身空间和时间开销会急剧增加一般只适用于非常小的输入规模。这道“本质上升子序列”问题完美地考察了选手对动态规划状态设计的理解以及对去重计数这一经典难点的把握。它告诉我们在面对复杂问题时有时跳出常规的“以i结尾”的思维定式从问题最终呈现的“本质”特征如结尾字符的值去定义状态往往能化繁为简。多练习这类题目对于提升在算法竞赛和面试中解决动态规划问题的能力大有裨益。 
长河君 · 2026/8/28 5:17:59 · 阅读 1.2k 动态规划解本质上升子序列：状态定义与去重计数详解
1. 项目概述从一道经典竞赛题说起最近在整理历年算法竞赛的经典题目时我又翻出了2020年第十一届蓝桥杯决赛JAVA B组的D题——“本质上升子序列”。这道题在当时的赛场上给不少选手带来了不小的挑战它看似是动态规划中“最长上升子序列”问题的变种但“本质不同”这个约束条件一下子把问题的复杂度提升了一个维度。很多朋友在初次接触时容易陷入重复计数的陷阱或者写出时间复杂度爆炸的暴力解法。今天我就以一个过来人的身份和大家一起彻底拆解这道题。我们不仅会探讨如何用动态规划高效求解更会深入分析“本质不同”的含义并对比多种解法的优劣最后分享一些在竞赛中快速识别和解决此类问题的实战技巧。无论你是正在备赛蓝桥杯的学生还是对算法感兴趣的开发者相信这篇深度解析都能让你对子序列类问题有更透彻的理解。2. 问题核心理解“本质上升子序列”在动手写代码之前我们必须把题目要求吃透。很多失误都源于对问题定义的模糊理解。2.1 题目定义与关键约束题目通常会给一个字符串s由小写字母组成要求我们找出其所有“本质不同的上升子序列”的个数并对结果取模。这里我们需要明确三个关键概念子序列由原字符串在不改变字符相对顺序的情况下删除某些字符也可以不删除得到的新序列。例如对于字符串“abc”“a”、“ac”、“b”都是它的子序列而“ca”不是。上升子序列对于字符串通常将字符的ASCII码值或字典序作为“大小”依据。一个子序列是“上升”的当且仅当它的每个字符都比前一个字符大严格递增。例如在“abc”中“ac”是上升的a c而“ba”不是。本质不同这是本题的核心难点。它指的是两个子序列的内容即字符序列本身不同。例如字符串“aba”中考虑以第一个‘a‘结尾和以第二个‘a‘结尾的、内容为“a“的子序列。虽然它们来自原字符串的不同位置但内容都是“a“因此它们被视为同一个本质子序列在计数时只算一次。注意本质不同与子序列的“来源位置”无关只与最终构成的字符序列有关。这是最容易混淆的地方。许多初学者会试图记录子序列的结尾索引来区分但这对于“本质不同”的判断是无效的。2.2 与经典LIS问题的本质区别最长上升子序列LIS问题是动态规划的入门经典。其标准动态规划定义dp[i]表示以第i个元素结尾的最长上升子序列长度状态转移方程为dp[i] max(dp[j]) 1 (其中 j i 且 nums[j] nums[i])。LIS问题关心的是“长度”的最大值。而本题“本质上升子序列个数”问题关心的是“数量”的累加。更重要的是LIS问题在计数时如果原序列有重复值以不同位置的相同值结尾的、长度相同的LIS会被视为不同的序列吗这取决于具体问法。但本题明确要求“本质不同”因此我们必须从状态定义上就杜绝重复内容的产生。这引导我们不能再简单地以“以某个位置结尾”来定义状态因为相同内容可能由不同位置产生。3. 动态规划思路深度拆解面对计数问题尤其是带“去重”要求的动态规划往往是首选。我们需要设计一个能规避重复计数的状态表示。3.1 状态定义的艺术既然“以位置i结尾”会导致重复我们尝试升维从字符本身入手。定义dp[i]表示以字符i这里i代表某个特定字符例如‘a‘‘b‘…结尾的、本质不同的上升子序列的个数。这个定义的精妙之处在于它将所有以相同字符结尾的子序列无论它们在原字符串中来自哪个位置都归并到了同一个状态里。这天然地解决了“本质不同”的去重要求。例如字符串“aba“中所有以‘a‘结尾的本质不同上升子序列其数量就存储在dp[‘a‘]中。3.2 状态转移方程的推导我们如何计算dp[i]呢假设当前遍历到原字符串中的字符ch。新建子序列字符ch本身可以作为一个长度为1的上升子序列。因此我们需要为dp[ch]增加1。接续已有子序列对于所有比ch小的字符smallChar即满足smallChar ch以smallChar结尾的任何本质不同上升子序列在其末尾添加上当前字符ch都能形成一个新的、以ch结尾的上升子序列。并且由于dp[smallChar]已经代表了所有以smallChar结尾的本质不同序列这些新序列也一定是本质不同的。去重关键这里会出现重复吗考虑字符串“abab“。当处理第二个‘b‘时它会尝试接在以‘a‘结尾的序列后面。而以‘a‘结尾的序列集合是固定的{“a“}。无论是第一个‘b‘还是第二个‘b‘接上后产生的新序列内容都是“ab“。如果我们简单地累加“ab“会被计算两次。但我们的状态dp[‘b‘]是以字符‘b‘结尾的序列个数。第一个‘b‘处理完后dp[‘b‘]已经包含了“b“和“ab“。当处理第二个‘b‘时我们如果再次将dp[‘a‘]的值加到dp[‘b‘]上就会导致“ab“被重复计算。因此正确的做法不是每次遇到字符都无脑累加。我们需要确保对于同一个字符ch在它多次出现时后续出现的位置不应该重复计算那些“由更早出现的相同字符ch已经计算过的”接续方案。解决方案是在遍历每个字符时我们计算的是“以本次出现的这个字符ch为结尾能新增多少本质不同的子序列”。然后用这个“新增量”去更新全局的dp[ch]。更具体地说我们可以用一个临时变量add来表示本次新增的数量。状态转移方程如下 假设当前遍历到字符ch。令add 1。这代表字符ch自身作为一个新序列。遍历所有字符c从‘a‘到比ch小的字符执行add dp[c]。这代表将所有以较小字符结尾的序列后接ch形成的新序列。那么add就代表了由当前这个位置的ch字符所带来的、全新的、以ch结尾的本质不同子序列的数量。最后将add累加到dp[ch]上dp[ch] add。这个过程中add的计算依赖于当前时刻的dp值即处理当前字符之前的状态。这保证了对于后面再次出现的相同字符ch‘它计算add时所基于的dp数组已经包含了之前字符ch所贡献的所有序列因此ch‘计算出的add不会包含重复项。3.3 初始化与最终结果初始化非常简单将所有字符对应的dp值设为0。 最终整个字符串遍历完成后我们需要的答案是所有可能的结尾字符所对应的序列数之和即sum(dp[‘a‘] 到 dp[‘z‘])。因为题目要求所有上升子序列无论以什么字符结尾都需要统计。实操心得在竞赛中为了编码方便我们通常会将字符映射到数组下标。例如dp[0]对应‘a‘dp[25]对应‘z‘。这样可以用循环轻松处理。另外由于结果可能很大题目通常会要求对一个大质数如1e97取模每一步加法运算后都要记得取模防止溢出。4. 算法实现与代码详解理论清晰后我们来看具体的代码实现。这里提供Java版本的核心代码并附上详细注释。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); String s sc.next(); int MOD 1000000007; // dp数组dp[i]表示以字符(‘a‘i)结尾的本质不同上升子序列个数 long[] dp new long[26]; // 遍历原字符串的每一个字符 for (int i 0; i s.length(); i) { int cur s.charAt(i) - ‘a‘; // 当前字符对应的索引 long add 1; // 新增数量初始为1代表当前字符自身作为一个序列 // 累加所有比当前字符小的字符结尾的序列数 for (int j 0; j cur; j) { add (add dp[j]) % MOD; } // 将本次新增的数量加到以当前字符结尾的总数上 dp[cur] (dp[cur] add) % MOD; } // 计算最终答案所有字符结尾的序列数之和 long ans 0; for (long num : dp) { ans (ans num) % MOD; } System.out.println(ans); sc.close(); } }代码逐行解析long[] dp new long[26];使用long类型防止中间结果溢出。数组下标0-25分别对应字符‘a‘到‘z‘。主循环for (int i 0; i s.length(); i)依次处理字符串中的每个字符。int cur s.charAt(i) - ‘a‘;将当前字符转换为0-25的索引。long add 1;add变量至关重要它代表由当前这个位置的字符新贡献的、以该字符结尾的序列数。初始值1代表该字符本身。内层循环for (int j 0; j cur; j)遍历所有比当前字符小的字符。dp[j]中存储了在遇到当前字符之前所有以字符j结尾的本质不同序列。这些序列后面加上当前字符都能形成新的、以当前字符结尾的序列且不会与之前产生的序列重复因为结尾字符不同或者序列内容因当前字符位置不同而本质不同。将这些数量累加到add中。dp[cur] (dp[cur] add) % MOD;将本次计算得到的add值累加到dp[cur]中。这一步更新了以cur字符结尾的总序列数。这正是去重的核心如果同一个字符在后面再次出现它计算add时使用的是更新前的dp数组因此不会重复计算之前已经生成过的、以该字符结尾的序列。最后遍历dp数组求和即为所有本质不同上升子序列的总数。时间复杂度分析外层循环遍历字符串长度为n内层循环固定为最多26次字符集大小。因此总时间复杂度为O(26 * n)对于n高达10^5的数据范围也完全可行。空间复杂度仅使用了一个大小为26的dp数组为O(1)。5. 对比分析与思路演进理解一种解法后再看看其他思路为何行不通或效率低下能加深我们对问题本质的理解。5.1 暴力枚举法及其局限性最直接的思路是枚举所有可能的子序列判断其是否上升且本质不同。枚举子序列的时间复杂度是O(2^n)n为字符串长度这显然是不可接受的。即使使用哈希集合如HashSet来自动去重枚举的指数级复杂度也无法处理稍大的数据n 30就非常困难。竞赛题的数据范围通常设计为迫使选手寻找更优算法。5.2 基于位置定义的动态规划为何失败如果我们定义dp[i]为以字符串中第i个位置字符结尾的本质不同上升子序列个数。状态转移时我们需要找到所有j i且s[j] s[i]的位置将dp[j]累加到dp[i]。但这里有一个致命问题不同的j1和j2位置如果s[j1] s[j2]那么以它们结尾的序列集合可能存在大量重复内容。例如“aba“以第一个‘a‘结尾的序列有{“a“}以第二个‘a‘结尾的序列也有{“a“}。在计算以‘b‘结尾的序列时dp[‘b‘]会分别加上dp[第一个‘a‘]和dp[第二个‘a‘]导致序列“ab“被计算两次。要基于位置dp去重需要在状态转移时进行复杂的判重通常需要用到集合导致时间复杂度劣化。5.3 基于字符定义的动态规划的优势我们采用的解法基于字符的dp之所以高效是因为它进行了状态压缩。它将原本可能分散在多个不同位置、但结尾字符相同的状态压缩成了一个状态。这个状态天然地代表了“所有以该字符结尾的本质不同序列”这个集合的总数。转移时我们不再关心这个序列来自原字符串的哪个具体位置只关心它的结尾字符和数量。这完美契合了“本质不同”的要求同时将内层循环的复杂度从O(n)降到了O(26)。6. 常见错误与调试技巧在实际编码和调试过程中我总结了一些常见的“坑点”。6.1 整数溢出问题这是竞赛中最常见的失分点之一。即使最终答案在取模后可能不大但中间累加过程(add dp[j])可能会超过int型的最大值约21亿。题目数据往往就是为此设计的。避坑技巧在Java中对于这类计数问题无脑使用long类型来定义dp数组和中间变量。并且在每一次加法运算后立即取模养成习惯。6.2 去重逻辑混淆有些同学理解了一半知道要用一个“总的”dp[char]但在更新时写成了dp[cur] add;而不是dp[cur] add;。这错误地将当前字符本次出现所产生的新序列完全覆盖了之前产生的所有序列。例如处理“ab“时遇到‘b‘add计算为1 dp[‘a‘] 2序列“b“和“ab“。如果使用覆盖赋值dp[‘b‘]最终为2这看似正确。但遇到“aba“处理最后一个‘a‘时add为1因为此时dp[‘b‘]是2但‘b‘不比‘a‘小所以不累加。如果覆盖赋值dp[‘a‘]最终为1但正确答案应该是2序列“a“第一个位置和“a“第三个位置本质相同只算一个序列“aba“不是上升的因为b a不满足。实际上dp[‘a‘]应该在第一个‘a‘时就已被更新为1遇到第三个‘a‘时add为1累加后dp[‘a‘]变为2代表以‘a‘结尾的序列有“a“和“?a“其中 ? 是小于a的字符这里没有所以就是“a“本身。这个例子恰好结果也是2但逻辑是错误的。正确的累加逻辑才能应对所有情况。6.3 模运算的细节取模运算(a b) % MOD在Java中没问题但如果你需要计算(a - b) % MOD且保证结果非负应该写成(a - b MOD) % MOD。虽然本题只有加法但这是一个重要的技巧。另外确保你的MOD值是int类型但参与运算的变量是long以防止乘法运算溢出。6.4 测试用例设计自己设计测试用例是调试的利器。可以从简单到复杂边界用例空字符串““如果题目允许答案应为0。单字符字符串“a“答案应为1只有“a“本身。无重复字符“abc“所有上升子序列为“a“,“b“,“c“,“ab“,“ac“,“bc“,“abc“共7个。可以用程序验证。有重复字符“aba“本质不同的上升子序列有“a“,“b“,“ab“。注意“ba“不是上升的b a? 不b a 是上升的但这里 b在a后面序列”ba”的顺序是原串中b(位置2)和a(位置3)23且‘b‘‘a‘满足上升等等仔细看字符串 “a b a“索引1 2 3。子序列”ba“取自索引2的b和索引3的ab a 不满足严格递增所以不是上升序列。。“aa“也不是上升的a 不大于 a。所以答案是3。复杂用例“abab“。可以手工推导或编写一个暴力枚举程序用于小数据来验证动态规划程序的结果。7. 竞赛实战策略与扩展思考在时间紧张的竞赛环境中如何快速解决此类问题7.1 快速识别模型看到“子序列”、“计数”、“本质不同”这些关键词就要立刻想到动态规划。如果还有“上升”递增条件那么状态定义很可能会与“结尾元素”相关。当发现重复元素可能导致重复计数时应果断放弃以“索引位置”结尾的定义尝试升维或改变状态定义例如用“以某个值结尾”来替代“以某个位置结尾”。这种“以值代位”的思路在去重计数问题中非常常见。7.2 模板化与编码速度对于这种字符集固定的问题26个小写字母可以准备一个模板dp数组长度26。双循环外层遍历字符串内层遍历比当前字符小的所有字符进行累加。使用long类型和即时取模。熟练后5分钟内完成编码和基本测试是可行的。7.3 问题变种与扩展字符集扩大如果不是小写字母而是0-9的数字或者ASCII码范围解法完全一样只需调整dp数组大小。下降子序列将内层循环条件从j cur改为j cur即可。非严格上升不下降将内层循环条件从j cur改为j cur。但要注意这可能会引入新的重复计数问题需要结合“本质不同”的定义仔细分析。通常对于非严格上升且本质不同需要在状态转移时只考虑最后一次出现的位置这需要额外的数组来记录每个字符上一次出现时的add值并在本次更新时减去上一次的贡献以避免同一内容序列因中间插入相同值而被重复计算。这比严格上升的情况要复杂一些。求具体方案如果题目要求输出所有本质不同的上升子序列而不仅仅是计数那么动态规划就需要记录路径。这通常需要用到集合或字典树来存储序列本身空间和时间开销会急剧增加一般只适用于非常小的输入规模。这道“本质上升子序列”问题完美地考察了选手对动态规划状态设计的理解以及对去重计数这一经典难点的把握。它告诉我们在面对复杂问题时有时跳出常规的“以i结尾”的思维定式从问题最终呈现的“本质”特征如结尾字符的值去定义状态往往能化繁为简。多练习这类题目对于提升在算法竞赛和面试中解决动态规划问题的能力大有裨益。