华为OD机试高频题：动态规划解决子序列计数问题

1. 项目概述从一道题看华为OD机试的“套路”与“解法”最近在帮几个准备华为OD机试的朋友做模拟练习发现“MELON的难题”这道题出现的频率相当高尤其是在所谓的“B卷”或“C卷”中被归类为中等难度。很多朋友第一次看到题目描述尤其是涉及到字符串按顺序统计某种模式时容易想复杂或者陷入暴力枚举的死胡同导致超时。这道题本身并不涉及特别高深的算法但它非常典型地考察了应聘者对基础数据结构的灵活运用、对问题边界条件的把控以及将实际问题抽象为可计算模型的能力——这恰恰是华为OD机试乃至很多大厂技术笔试的核心考察点。简单来说“MELON的难题”通常描述为给定一个字符串s需要找出所有满足特定顺序条件的子序列注意是子序列subsequence不是子串substring并统计其数量。这个“特定顺序条件”往往与字符的排列有关例如“MELON”这几个字母在子序列中必须以M-E-L-O-N的顺序出现但中间可以间隔任意其他字符。题目会要求你计算这样的子序列有多少个。这听起来有点像在字符串里找“模式”但又不是简单的字符串匹配。这道题适合所有正在准备华为OD机试尤其是目标岗位对编程能力有明确要求的同学。无论你是用Python、Java还是C理解其背后的核心思想——动态规划——远比死记硬背代码更重要。接下来我会以从业者的视角拆解这道题的解题思路并给出三种语言的实现细节、避坑指南以及一些只有真正调试过才能发现的“暗礁”。2. 核心思路拆解为什么动态规划是“唯一正解”面对“统计满足特定顺序的子序列数量”这类问题初学者最容易想到的方法是回溯或DFS枚举所有可能的子序列然后检查是否符合顺序。假设字符串长度为n子序列的数量是2^n量级当n较大时比如超过20这种指数级复杂度是完全不可接受的。机试对时间限制通常非常严格这就要求我们必须寻找更优的解法。2.1 将问题转化为状态转移我们以寻找“MELON”这个单词作为模式串pattern在字符串s中作为子序列出现的次数为例。定义模式串P “MELON”其长度为m5。关键思路是我们并不需要关心子序列具体由哪些位置的字符构成我们只关心“当前已经匹配到了模式串的哪一位”。我们可以定义一个状态数组dp其中dp[j]表示在遍历输入字符串s的某个前缀时能够匹配到模式串P的前j个字符的子序列有多少种。更具体一点dp[0]始终为1。这表示“匹配到0个字符”即一个字符都没匹配上的方式只有一种什么都不选。这是我们的初始状态。对于s中的每一个字符c我们从后往前更新dp数组为什么从后往前后面会解释。对于j从m到1如果c P[j-1]因为索引从0开始那么当前字符c可以用来匹配模式串的第j位。此时所有能匹配到前j-1位的子序列在末尾加上这个字符c就构成了新的、能匹配到前j位的子序列。因此dp[j]的新值应该加上dp[j-1]。最终dp[m]就是我们想要的答案匹配整个模式串“MELON”的子序列总数。注意这里“从后往前”更新至关重要。如果从前往后更新会出现重复计数的问题。例如字符串“MM”模式“M”。从前往后更新时遇到第一个‘M’dp[1] dp[0](1-1)。遇到第二个‘M’时dp[1]再次加上dp[0]此时dp[0]还是1结果dp[1]2。但实际上在“MM”中“M”作为子序列只有两个选择第一个M或选择第二个M这个结果是对的。但考虑模式“AB”和字符串“AAABBB”从前往后更新会导致复杂的重复计算。而从后往前更新可以保证对于当前字符s[i]我们用它来更新dp[j]时所依赖的dp[j-1]是截止到上一个字符s[i-1]为止的状态不会包含当前字符s[i]本身也用来更新dp[j-1]的情况从而保证了每个字符在本次扫描中只被使用一次来扩展子序列。这是动态规划中处理“选择当前物品”类问题的经典技巧。2.2 算法复杂度分析我们只需要遍历一次输入字符串s长度为n。在遍历每个字符时我们需要从m到1更新dp数组这是一个O(m)的操作。因此总的时间复杂度是O(n * m)。由于m模式串长度通常是一个很小的常数比如“MELON”是5所以算法几乎是O(n)线性的效率极高。空间复杂度是O(m)只需要一个一维数组也非常优秀。这个算法的精妙之处在于它通过动态规划状态巧妙地避开了对具体子序列的枚举将计数问题转化为可叠加的状态转移这正是面试官希望看到的对算法思想的掌握而不是蛮力破解。3. 多语言实现与细节剖析理解了核心动态规划思想后实现起来就相对直接了。但不同语言在细节处理、数据溢出等方面各有讲究这也是机试中容易丢分的地方。3.1 Python实现简洁与陷阱Python以其简洁著称非常适合快速实现算法原型。def count_subsequences(s: str, pattern: str) - int: 统计字符串s中pattern作为子序列出现的次数。 m len(pattern) # dp[j] 表示匹配到pattern前j个字符的子序列数 dp [0] * (m 1) dp[0] 1 # 空子序列只有一种方式 for ch in s: # 必须从后往前更新避免重复计数 for j in range(m, 0, -1): if ch pattern[j - 1]: dp[j] dp[j - 1] return dp[m] # 示例在字符串中找“MELON” s MXXXELOOOONXX pattern MELON result count_subsequences(s, pattern) print(f子序列数量: {result})Python实现的注意事项列表初始化与索引dp数组长度为m1dp[0]作为基础。访问pattern[j-1]时要注意下标转换。整数溢出问题在Python中整数是任意精度的所以通常不用担心结果太大导致溢出。这是Python在机试中的一个优势。但在极端情况下结果可能异常巨大题目有时会要求对结果取模例如10^97。如果题目有取模要求务必在每次加法后取模dp[j] (dp[j] dp[j-1]) % MOD。循环顺序内层循环for j in range(m, 0, -1):是核心务必是从m递减到1。写成range(1, m1)就是错误答案。字符编码题目输入通常是纯英文字符串直接用比较即可。如果涉及中文或其他复杂字符Python 3的字符串处理是没问题的。一个常见的“坑”有同学可能会先判断if ch in pattern然后再去更新以为能优化。但这样做是错误的因为ch可能等于模式串中的多个字符比如模式是“ABA”字符‘A’能匹配第一位和第三位我们的更新逻辑依赖于当前字符ch与pattern[j-1]的精确比较并且需要从后往前更新来保证状态正确。提前过滤会破坏这个逻辑。3.2 Java实现严谨与性能Java实现需要更关注数据类型和可能的溢出。public class MelonProblem { public static long countSubsequences(String s, String pattern) { int m pattern.length(); // 使用long类型防止溢出 long[] dp new long[m 1]; dp[0] 1L; for (int i 0; i s.length(); i) { char currentChar s.charAt(i); // 从后往前更新dp数组 for (int j m; j 1; j--) { if (currentChar pattern.charAt(j - 1)) { dp[j] dp[j - 1]; } } } return dp[m]; } public static void main(String[] args) { String s MXXXELOOOONXX; String pattern MELON; long result countSubsequences(s, pattern); System.out.println(子序列数量: result); } }Java实现的注意事项数据类型的选取这是Java实现中最关键的一点。即使结果在int范围内中间累加过程dp[j] dp[j-1]也可能导致int溢出。因此dp数组必须使用long类型。如果题目明确说明结果很大需要取模那么取模操作也应在每次加法后进行dp[j] (dp[j] dp[j-1]) % MOD此时dp数组可以用int但MOD运算要注意使用long临时变量避免乘法溢出。字符串访问使用charAt(i)方法访问字符效率较高。不要在循环内部调用s.substring(i, i1)这会创建大量临时字符串对象影响性能。数组初始化Java会默认将long数组初始化为0dp[0]1需要显式设置。输入处理在机试环境中输入通常来自Scanner或BufferedReader。务必处理好可能的输入格式比如字符串可能包含空格题目会说清楚使用nextLine()还是next()要看清题目。性能调优点在极少数对性能要求变态的题目中如果模式串很长比如几十内层循环O(m)可能成为瓶颈。可以考虑用一个MapCharacter, ListInteger预先存储模式串中每个字符出现的位置列表逆序。这样遍历s时对于字符c直接拿到它在pattern中的所有位置posList然后只更新这些位置对应的dp值。但这属于进阶优化在“MELON”这种m5的情况下完全没必要代码反而更复杂。3.3 C实现效率与控制C给了开发者最大的控制权同时也要求对细节有最严格的把握。#include iostream #include string #include vector using namespace std; long long countSubsequences(const string s, const string pattern) { int m pattern.size(); // 使用long long防止溢出 vectorlong long dp(m 1, 0); dp[0] 1; for (char c : s) { // 从后往前更新 for (int j m; j 1; --j) { if (c pattern[j - 1]) { dp[j] dp[j - 1]; } } } return dp[m]; } int main() { string s MXXXELOOOONXX; string pattern MELON; long long result countSubsequences(s, pattern); cout 子序列数量: result endl; return 0; }C实现的注意事项整数类型在C中int通常是32位很容易溢出。务必使用long long来定义dp数组和返回值。这是C机试中最常见的错误之一。参数传递函数参数使用const string常量引用避免不必要的字符串拷贝提升效率。循环变量使用前缀自减--j理论上比后缀自减j--效率稍高对于内置类型编译器可能优化掉区别但养成好习惯。范围循环for (char c : s)清晰且不易出错。输入输出机试环境可能关闭了cin/cout与stdio的同步导致cin/cout变慢。如果遇到大量数据输入输出超时可以考虑使用scanf和printf或者在一开始加上ios::sync_with_stdio(false); cin.tie(nullptr);来加速。内存与初始化vectorlong long dp(m 1, 0);会将所有元素初始化为0然后再设置dp[0]1。也可以直接用vectorlong long dp(m 1); dp[0] 1;但这样其他元素是未初始化的对于long long可能是0但不保证显式初始化是更安全的做法。一个深度技巧如果模式串字符集很小比如只有大写字母我们可以用空间换时间。用一个大小为26的数组lastPos记录每个字母在模式串中最后一次出现的位置从后往前看。然后在遍历s时对于字符c我们只需要更新dp[lastPos[c]]和dp[lastPos[c]-1]不这个思路不对。因为一个字符可能在模式串中出现多次如“ABA”中的‘A’。更通用的优化是“位置列表”法和Java里提到的一样但C实现起来更需要注意内存访问效率。4. 从解题到举一反三同类问题与变种掌握了“MELON的难题”的核心解法你实际上掌握了一类“统计子序列”问题的通解。面试官非常喜欢考察举一反三的能力。4.1 变种一统计不同的子序列原题是统计作为子序列出现的次数允许重复。如果问题变为给定字符串s和t计算在s的子序列中等于t的不同子序列的个数。这里的“不同”指的是子序列选取的字符索引集合不同即使内容看起来一样。例如s “rabbbit”,t “rabbit”。答案应该是3。如何解 实际上我们上面实现的动态规划方法天然就是计算“不同子序列”数量的因为我们的状态dp[j]定义就是“有多少种不同的方式匹配到t的前j个字符”。每一步累加都是在累加不同的来源即选择不同的s[i]来匹配t[j]。所以代码完全一样。4.2 变种二带有权值或代价的子序列如果每个字符有一个权值比如分数要求找出权值和最大/最小的满足条件的子序列。这时我们的dp状态就需要从“计数”转变为“最优权值”。dp[j]可以定义为匹配到t的前j个字符时所能获得的最大权值和。状态转移方程可能变为dp[j] max(dp[j], dp[j-1] weight(s[i]))当s[i] t[j-1]时。这变成了一个最优子序列问题。4.3 变种三模式串是给定的但需要处理多个查询题目可能给出一个很长的字符串s和成千上万个不同的短模式串t要求对每个t快速回答其在s中作为子序列出现的次数。这时对每个t都做一次O(n*|t|)的DP就太慢了。一种高效的预处理方法是构建一个“下一个位置”表next_pos。next_pos[i][c]表示在s的位置i之后字符c下一次出现的位置。构建这个表需要O(n * 字符集大小)的时间。对于每个查询t我们可以用双指针在s上“跳跃”匹配初始化指针p -1然后遍历t的每个字符c将p更新为next_pos[p1][c]。如果某次更新后p超出字符串范围则匹配失败如果成功遍历完t则存在至少一个子序列。但这种方法只能判断是否存在要计数仍然很困难。对于计数可能需要结合自动机或更复杂的数据结构这通常超出了普通机试的范围。4.4 如何识别这类问题在机试或面试中当你看到以下关键词时就要联想到我们今天讨论的DP模型“子序列”subsequence而不是“子串”substring。“统计数量”count the number of。“按顺序”in order。模式串相对较短通常不超过10-20。输入字符串可能很长n可达10^4甚至10^5。5. 机试实战技巧与避坑指南基于多次模拟和实战经验我总结了一些在华为OD机试中解决此类字符串/DP问题的通用技巧和常见陷阱。5.1 输入输出处理不同语言这是机试的第一道坎处理不好会导致程序根本读不到正确数据。Python最常用input()。如果输入有多行且已知行数可以用for _ in range(n): s input()。如果一行有多个数字或字符串用list(map(int, input().split()))或input().split()。大坑题目有时说“输入包含空行”直接用input()会读到空字符串可能需要用sys.stdin.read().splitlines()来灵活处理。Java推荐BufferedReaderInputStreamReader效率远高于Scanner。BufferedReader br new BufferedReader(new InputStreamReader(System.in)); String s br.readLine(); // 读取多个数字 String[] parts br.readLine().split( ); int a Integer.parseInt(parts[0]);注意处理IOException。C用cin 读取单词用getline(cin, str)读取整行。混合使用时在cin 后如果紧跟getline需要先用cin.ignore()清除缓冲区里的换行符。对于大量数据用scanf。实操心得在开始写核心逻辑前先用样例输入测试你的IO代码确保能正确解析。很多同学算法想对了却跪在IO上。5.2 调试与测试用例设计机试环境通常不允许使用本地IDE的调试器因此“打印调试”和设计有效的测试用例至关重要。设计简单用例空字符串s“”, pattern“MELON”结果应为0。模式串为空s“ABC”, pattern“”根据定义空串是任何字符串的子序列且只有一种方式什么都不选结果应为1。我们的算法中dp[0]1最终返回dp[0]1符合。完全匹配s“MELON”, pattern“MELON”结果应为1。重复字符s“MMMM”, pattern“MM”。结果是C(4,2)6不对子序列不要求连续从4个M里选2个确实是6种组合。可以用我们算法验证。无匹配字符s“ABC”, pattern“XYZ”结果为0。打印关键变量在DP循环中可以打印出每处理一个字符后的dp数组状态。这对于验证状态转移是否正确非常直观。def count_subsequences_debug(s, pattern): m len(pattern) dp [0]*(m1) dp[0]1 for i, ch in enumerate(s): print(f处理 s[{i}]{ch}:) old_dp dp[:] # 拷贝一份用于对比 for j in range(m, 0, -1): if ch pattern[j-1]: dp[j] dp[j-1] # 打印更新前后的变化 for j in range(m1): if dp[j] ! old_dp[j]: print(f dp[{j}] {old_dp[j]} - {dp[j]}) print(f 当前dp数组: {dp}) return dp[m]5.3 时间与空间复杂度估算在写出代码前心里要对复杂度有数。对于本题O(n*m)的算法如果n 10^5,m 10那么n*m 10^6运算量很小完全可行。如果n 10^3,m 10^3那么n*m 10^6也还可以。如果n和m都在10^4量级n*m可能达到10^8在2秒的时间限制下C可能勉强通过Python和Java就非常危险了。这时就需要考虑优化如之前提到的“位置列表”优化将内层循环从O(m)降到O(该字符在模式串中出现次数)。在机试中如果看到数据范围很大就要警惕。先写一个暴力解法保底如果时间允许同时思考更优的DP或贪心策略。5.4 代码风格与注释虽然机试主要看结果但清晰的代码结构和必要的注释能体现你的专业素养尤其在边界条件处理处加上注释。给函数和变量起有意义的名字。在关键步骤特别是容易出错的地方如DP数组初始化、循环顺序、取模操作写上简短注释。处理好函数返回值特别是当结果可能非常大时确认返回类型是否正确。6. 常见问题与排查实录这里记录了我自己和朋友们在练习这道题时真实踩过的坑以及排查思路。问题1结果总是比预期大很多或者出现负数。排查这几乎是整数溢出的典型症状。在Java和C中即使最终结果在int范围内DP过程中的累加也可能溢出。int溢出后会变成负数再累加可能导致结果混乱。解决立刻将dp数组的数据类型从int改为longJava或long longC。在Python中虽然不会溢出但如果题目要求取模忘记取模也会导致结果巨大虽然不会报错但判题系统会认为答案错误。问题2对于某些测试用例结果比预期小1。排查检查dp[0]是否初始化为1。dp[0]1代表“匹配0个字符”的方案数即空子序列。这是动态规划的“种子”如果设为0所有结果都会是0。问题3当模式串中有重复字符时结果不正确。排查99%的原因是内层DP更新顺序错了。你很可能写成了从前向后更新for j in range(1, m1): # 错误从前向后 if ch pattern[j-1]: dp[j] dp[j-1]对于模式“ABA”和字符串“ABABA”从前更新会重复计数。务必改为从后向前更新。问题4在Python中对于超长字符串例如10^5程序运行超时。排查虽然算法是O(n*m)但Python的循环本身比较慢。m如果比较大比如10010^5 * 100 10^7次循环和加法在Python中可能接近时间极限。优化尝试尝试使用PyPy解释器如果机试环境支持它的循环性能通常比CPython好。使用局部变量。将pattern、dp、m等在循环外赋值给局部变量可以轻微提升速度。如果模式串字符集有限如只有大写字母可以尝试用“位置列表”法优化减少内层循环次数。但代码复杂度会增加需权衡。问题5如何处理模运算1e97这是一个非常常见的附加要求。关键点在于每次加法后都要取模而不是最后才取模。因为中间结果就可能溢出即使在Python中最后取模虽然不会溢出但中间结果可能变得非常大影响计算效率。MOD 10**9 7 def count_subsequences_mod(s, pattern): m len(pattern) dp [0] * (m 1) dp[0] 1 for ch in s: for j in range(m, 0, -1): if ch pattern[j - 1]: dp[j] (dp[j] dp[j - 1]) % MOD # 每次加法后取模 return dp[m] % MOD在Java和C中即使使用了long为了符合题目要求并保证一致性也应该在每次加法后取模。问题6题目输入格式有变化怎么办比如题目可能说“字符串s由空格分隔的多个单词组成需要先连接起来”。或者模式串t不是直接给出而是需要从输入中解析。这时一定要仔细阅读题目描述根据要求编写预处理代码。一个技巧是先写一个solve()函数它接收处理好的s和pattern返回答案。这样主函数就只负责复杂的输入解析逻辑清晰也便于调试。最后这道“MELON的难题”就像一把钥匙帮你打开了一类动态规划计数问题的大门。其核心在于定义出“以当前匹配长度作为状态”的DP数组并通过巧妙的更新顺序来保证计数不重不漏。在华为OD机试中类似的题目可能换个外壳出现比如统计“逆序对”、“特定和的子序列”等等但只要你掌握了状态定义和转移的思想就能从容应对。多练习多总结把每种遇到的题型和对应的DP模型关联起来形成自己的解题工具箱这才是通过机试、乃至后续面试的不二法门。