动态规划去重计数：从LIS到本质上升序列的状态定义与增量更新

1. 项目概述从一道国赛真题看动态规划的本质最近在整理蓝桥杯的历年真题翻到了2020年国赛Java大学A组的这道“本质上升序列”。说实话第一次看到题目描述时我也愣了一下因为它和我们平时刷的“最长上升子序列”LIS问题很像但又多了一层“本质不同”的要求。这恰恰是国赛题目的魅力所在它不会直接考你模板而是把一个经典问题套上一个新壳子考察你是否真正理解了算法核心并能灵活变通。这道题就是一个绝佳的例子它用“本质上升序列”这个概念把动态规划DP中“状态定义”和“去重”这两个关键点揉在了一起非常考验基本功和思维严谨性。简单来说题目是给你一个字符串比如 “lanqiao”让你找出所有“本质不同”的上升子序列的个数。这里的“上升”指的是子序列中字符的ASCII码严格递增“本质不同”指的是即使两个子序列由原字符串中不同位置的字符组成但只要它们看起来一模一样比如都是 “an”那就算作同一个。最终要输出这个数量。这题如果暴力枚举所有子序列再去重时间复杂度是指数级的字符串长度稍微大点比如到100就完全不可行。所以动态规划几乎是唯一的正解。接下来我就结合自己的解题和教学经验把这道题的动态规划解法掰开揉碎了讲清楚重点不止在于写出状态转移方程更在于理解为什么这样定义状态以及如何处理“本质不同”这个棘手的条件。2. 核心思路拆解状态定义与去重逻辑的博弈面对任何动态规划问题第一步也是最关键的一步就是定义状态。状态定义得好问题就解决了一半定义得不好要么解不出来要么代码极其复杂。2.1 经典LIS思路的局限性我们最熟悉的上升子序列问题是求最长长度状态通常定义为dp[i]表示以第i个字符结尾的最长上升子序列的长度。转移方程是dp[i] max(dp[j]) 1其中j i且s[j] s[i]。但如果把问题换成“求所有上升子序列的个数”一个很自然的想法是定义cnt[i]为以第i个字符结尾的上升子序列的个数。那么cnt[i]似乎应该等于所有满足j i且s[j] s[i]的cnt[j]之和再加上单独以s[i]自身作为一个序列的情况即1。这个思路对吗我们用一个简单例子s “aba”来测试一下。按照ASCII码‘a’97, ‘b’98。对于i0(‘a’):cnt[0] 1(只有”a”)。对于i1(‘b’): 前面有s[0]‘a’ ‘b’所以cnt[1] cnt[0] 1 1 1 2。这两个序列是”b” 和 “ab”。对于i2(‘a’): 前面没有字符比 ‘a’ 小ASCII码相等或更大都不行所以cnt[2] 1(只有”a”)。那么所有上升子序列的总数就是cnt[0] cnt[1] cnt[2] 1 2 1 4。这4个序列是”a”(i0), “b”, “ab”, “a”(i2)。问题来了这里有两个 “a”它们被视为不同的序列因为来自原字符串的不同位置。但这道题要求“本质不同”即只要序列字符串相同就算一个。所以正确答案应该是3个”a”, “b”, “ab”。你看经典的数量统计方法直接失效了因为它无法处理“来自不同位置的相同字符形成的相同子序列”带来的重复计数。这就是本题的核心难点。2.2 破局关键以字符为终点的状态定义为了从根源上避免重复我们必须改变状态定义的角度。不能以“字符串中的位置 i”作为状态因为同一个字符可能出现在多个位置比如例子中的 ‘a’。我们应该以“字符本身”作为状态。定义dp[c]表示以字符 c 结尾的、所有本质不同的上升子序列的个数。这里的 c 是 char 类型我们可以用一个长度为 128 或 256 的数组来表示覆盖ASCII码范围。这个定义的精妙之处在于它将所有以相同字符结尾的序列无论这个字符在原始字符串的哪个位置出现都归并到了同一个状态里。这样在统计总数时自然就完成了“本质不同”的去重。那么状态如何转移呢我们遍历原始字符串的每一个字符s[i]。对于当前字符s[i]它自己可以作为一个独立的子序列。它可以接在所有以小于s[i]的字符结尾的子序列后面形成新的子序列。但是直接累加会带来新的问题重复累加。假设字符串是“abac”当我们处理到第二个 ‘a’ (i2) 时它尝试接在 ‘b’ (i1) 后面。但第一个 ‘a’ (i0) 在处理时也已经接过 ‘b’ 了如果 ‘b’ 在 ‘a’ 后面的话。如果简单地dp[‘a’] dp[‘b’]那么dp[‘b’]里包含的序列会被重复加到dp[‘a’]中。2.3 动态维护与增量更新正确的做法是在遍历字符串的过程中动态地、以当前字符s[i]为终点来更新所有相关的dp值。具体步骤如下我们维护一个数组dp[128]初始全为0。 遍历字符串s的每个字符ch s[i]我们计算一个temp变量它代表“在遇到当前这个ch之前能够转移到ch上的、所有本质不同的序列总数”。也就是所有 ASCII 码小于ch的字符c’对应的dp[c’]之和。那么以当前这个ch结尾的、新的本质不同的序列有多少呢它等于两部分第一部分ch自身作为一个序列贡献了 1。第二部分ch可以接在前面计算出的temp个序列后面形成temp个新序列。所以对于当前遇到的这个ch它带来的全新序列数量是1 temp。关键一步将这个数量(1 temp)加到dp[ch]上。注意是“加等”不是“等于”。因为dp[ch]可能已经被字符串中前面出现的相同字符ch更新过了当前字符ch带来了新的、以它结尾的序列这些序列和之前的序列是“本质不同”的因为至少末尾这个ch的位置是新的并且形成的序列字符串可能因为中间字符不同而不同但即使相同也被我们以字符为维度的状态定义自动归并了。这个“加等”操作就是动态规划过程中对状态的增量更新它确保了所有以字符ch结尾的序列都被不重不漏地统计在dp[ch]中。最后整个字符串遍历完后我们需要的答案就是sum(dp[0..127])即所有以任意字符结尾的本质不同上升子序列的数量之和。注意这里有一个非常重要的细节也是容易出错的地方。在遍历到字符ch时计算temp即小于ch的字符对应的 dp 值之和必须基于本次更新前的dp数组状态。如果基于正在更新的dp数组就会发生“自我累加”的错误导致计数偏多。在具体实现时通常需要在循环内部用一个临时变量来累加temp或者采用特定的遍历顺序来避免。3. 算法实现与代码逐行解析理解了核心思路我们来看Java代码实现。我会先给出完整代码然后逐段解析关键点。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); String s sc.next(); sc.close(); // dp数组下标对应字符的ASCII码值表示以该字符结尾的本质不同上升子序列个数 long[] dp new long[128]; // 使用long防止大数溢出 char[] chars s.toCharArray(); for (char ch : chars) { long temp 1; // 当前字符自身作为一个序列初始为1 // 累加所有小于当前字符的dp值 for (int c 0; c ch; c) { temp dp[c]; } // 关键将temp加到dp[ch]上表示新增了这么多以ch结尾的序列 dp[ch] temp; } long ans 0; for (long num : dp) { ans num; } System.out.println(ans); } }3.1 数据结构与初始化long[] dp new long[128];这里定义了状态数组。为什么是128因为题目字符串由小写字母组成ASCII码范围在97(‘a’)到122(‘z’)之间128足够覆盖。使用long类型是蓝桥杯比赛的常见技巧因为结果可能很大用int可能会溢出。这是一种防御性编程思维。char[] chars s.toCharArray();将字符串转为字符数组比直接使用s.charAt(i)在循环中效率稍高也更便于遍历。3.2 核心循环逻辑详解for (char ch : chars)遍历字符串中的每一个字符。long temp 1;这是本解法的精髓之一。temp变量代表的是当前字符ch所带来的、全新的本质不同序列的数量。初始值1就代表了序列“ch”即当前字符本身。这个temp会在内层循环中累加。for (int c 0; c ch; c) { temp dp[c]; }这是动态规划的转移过程。它遍历所有ASCII码小于ch的字符c。dp[c]中存储的是在遇到当前ch之前所有以字符c结尾的本质不同序列。那么这些序列的每一个在后面加上当前的ch就形成了一个新的、以ch结尾的上升子序列。所以temp需要把这些序列的数量都加进来。为什么是c ch而不是c ch因为题目要求“严格递增”所以子序列中前一个字符必须严格小于后一个字符相等是不行的。dp[ch] temp;这是状态更新。将本次计算得到的、由当前这个ch带来的所有新序列temp个累加到dp[ch]中。注意是不是。这行代码实现了状态的聚合无论字符ch在字符串中出现多少次所有以它结尾的序列都被汇总到了dp[ch]这个状态里。3.3 结果统计与输出遍历结束后dp数组中每个元素dp[c]都表示以字符c结尾的所有本质不同上升子序列的个数。那么整个字符串的所有本质不同上升子序列总数就是dp数组中所有元素的和。用一个循环累加即可。3.4 复杂度分析时间复杂度O(n * 128)。外层循环遍历字符串长度为 n内层循环最多遍历128次常数。因此总复杂度是 O(n)对于 n 达到 10^5 的数量级也完全可行。空间复杂度O(128)即常数空间非常高效。4. 深入理解与经典LIS问题对比为了加深理解我们把这道题和经典的“最长上升子序列LIS”问题放在一起对比。特性经典LIS问题 (求长度)本质上升序列问题 (求个数)状态定义dp[i]: 以第i个元素结尾的最长上升子序列长度。dp[c]: 以字符c结尾的本质不同上升子序列个数。状态维度与输入序列位置强相关。与字符值相关与位置无关。去重考量无需去重只关心长度。核心难点需在状态定义中规避。转移方程dp[i] max(dp[j]) 1, 其中j i 且 arr[j] arr[i]。dp[ch] 1 sum(dp[c]) for all c ch(对每个出现的ch)。结果max(dp[i])sum(dp[c])核心思想最优子结构寻找前驱中最优的。计数与聚合将相同结尾的序列聚合计数避免重复。通过对比可以看出“本质上升序列”问题虽然脱胎于LIS但其核心已从“求最优解”转变为“计数并去重”。状态定义从“索引维度”切换到“值域维度”是解决此类去重计数问题的常用技巧。这提醒我们动态规划没有一成不变的模板深刻理解问题本质灵活定义状态才是解题的关键。5. 常见错误与排查指南在实际编写和调试这道题时我遇到过也见过学生们常犯的一些错误。这里列出来方便大家避坑。5.1 错误类型一状态定义错误导致重复计数错误代码示例long[] dp new long[128]; for (char ch : chars) { long sum 0; for (int c 0; c ch; c) { sum dp[c]; } // 错误使用赋值 而不是加等 dp[ch] sum 1; }错误分析这样做dp[ch]每次都会被覆盖。如果字符ch在字符串中出现多次只有最后一次出现时的计算结果会被保留之前出现的ch所形成的新序列都被丢弃了导致结果偏小。排查方法用简单重复字符串测试如“aaa”。理论上上升子序列只有“a”这一种单个字符数量是1。但上面的错误代码在处理第三个 ‘a’ 时dp[‘a’]会被重新赋值为1最终总和是1看似正确但过程是错的。换一个“aba”正确结果是3但此错误代码可能得到错误结果。关键检查点遇到重复字符时dp值是否在增加。5.2 错误类型二转移过程逻辑错误错误代码示例for (char ch : chars) { dp[ch] 1; // 先加上自己 for (int c 0; c ch; c) { // 错误直接让 dp[ch] 累加 dp[c] dp[ch] dp[c]; } }错误分析这段代码的问题在于内层循环的dp[c]可能已经包含了当前字符ch之前出现时所贡献的序列。这会导致重复转移。例如对于“ab”处理 ‘b’ 时dp[‘a’]是1。这没问题。但对于“aba”处理第二个 ‘a’ 时它会去加dp[‘b’]而此时的dp[‘b’]已经包含了序列“ab”。那么“ab” ‘a’会形成“aba”但注意“a” ‘b’ ‘a’并不是一个上升序列因为 ‘a’ ‘b’ 但 ‘b’ ‘a’ 不满足严格递增。更严重的这种累加方式会导致序列被错误地拼接。正确的做法应该像标准答案那样用一个临时变量temp来收集所有“前驱状态”的和然后一次性加到dp[ch]上这个temp的计算是基于本次更新前的dp数组快照。排查方法使用“abc”这样的小字符串手动模拟dp数组的变化过程画图跟踪每个步骤后dp的值与正确算法进行对比。5.3 错误类型三数据类型溢出错误代码示例int[] dp new int[128]; // 使用int ... int ans 0; for (int num : dp) ans num; System.out.println(ans);错误分析蓝桥杯的测试数据往往会有边界情况。本质不同上升子序列的数量可能是一个非常大的数。例如一个由100个严格递增字符组成的字符串其本质不同上升子序列数量是 2^100 - 1这远远超出了int甚至long的范围不过本题官方数据在 long 范围内。使用int在中间计算或最终求和时极易溢出得到负数或错误结果。排查方法在涉及可能大数的计数问题时养成使用long的习惯。如果题目暗示或明确可能更大则需要考虑使用BigInteger。5.4 调试与验证技巧小数据测试从最短的字符串开始测试如“”(空串可能规定为0或1需看题意)“a”,“aa”,“ab”,“aba”,“abc”。自己手算预期结果与程序输出对比。打印中间状态在循环中打印每个字符处理前后的dp数组主要看字母对应的位置观察其变化是否符合逻辑。对比暴力法对于长度非常小n 10的字符串可以写一个暴力DFS枚举所有子序列并用Set去重的程序用来验证动态规划结果的正确性。这是验证算法正确性的“金标准”。关注初始化确保dp数组初始化为0。long temp1;这步的初始化在循环内正确完成。6. 举一反三动态规划去重计数问题的通用思路这道“本质上升序列”题提供了一个非常好的范式用于解决一类“带去重的计数”问题。我们可以总结出以下通用思路识别重复源首先要分析清楚重复计数从何而来。在这道题里重复来自于“不同位置相同字符形成的相同子序列”。在其他问题里重复可能来自于不同的排列顺序形成相同的组合、不同的选择路径到达相同的状态等。重新定义状态合并重复项为了在计数时自动去重我们需要设计一种状态定义使得会导致重复的那些不同“路径”或“来源”最终都映射到同一个状态值上。本题中将从“以位置结尾”改为“以字符值结尾”就是成功合并了重复项。在其他问题中可能需要按“排序后的集合”、“某种规范化的形式”来定义状态。设计增量更新在动态规划过程中当我们处理一个新的“元素”如本题中的一个新字符时需要计算这个新元素能带来多少新的、不重复的方案。然后将这些新方案累加到对应的状态中而不是覆盖。这个“新方案数”的计算通常基于处理当前元素时所有“前驱状态”的当前值。思考转移顺序状态的更新顺序要确保在计算当前状态时它所依赖的前驱状态已经是更新完成的最新值对于最优化问题或者是更新前的稳定值对于去重计数问题如本题需要更新前的快照。这常常决定了是顺序遍历、逆序遍历还是需要额外的临时数组。遇到类似的题目比如计算一个数组中有多少种不同的上升子序列元素可能重复、计算字符串中不同子序列的数量不一定是上升的等都可以尝试套用“定义以结果为导向的状态 增量更新避免重复”这个思维框架。这道2020年蓝桥杯国赛真题代码虽然简短但蕴含的动态规划思想却非常深刻。它告诉我们刷题不能只记模板更要理解状态定义如何影响问题的可解性。下次再遇到“求个数”且需要“去重”的动态规划题不妨先想想我的状态定义能否让那些本该被视为同一个的东西自然地被归到同一个状态里