1. 问题描述与核心思路拆解1.1 先把这个题目的场景讲清楚“密码脱落问题”不是一道生僻的偏题怪题恰恰相反它是动态规划入门阶段非常有代表性的经典题在很多学校的OJ、课程设计和面试题库里都能看到它的身影。题目本身借了一个考古背景一串由字母或数字组成的密码原本是一个回文串但因为年代久远部分字符脱落了只剩下现在这一串残缺的序列。现在要根据剩下的序列算出最少脱落了多少个字符。很多刚接触这个题的同学第一反应是那我怎么知道原来长什么样确实题目没有直接给出原密码只给了残缺序列。但细想一下会发现问题的关键不是复原原字符串而是找残留串里的信息——如果某一段字符原本就是回文的那这一段就“没怎么脱落”脱落得越多剩下的东西就越不“回文”。所以这个问题的本质是求给定字符串的最长回文子序列长度。什么叫“回文子序列”简单说从原串里挑出一部分字符保持它们在原串中的相对顺序不变拼出来的新串如果是回文从前往后读和从后往前读一样那它就是原串的一个回文子序列。注意子序列和子串不一样子串必须是连续的子序列允许跳着取。比如ABCBD的子序列ABD就不是回文但ABA是取第1、2、4个字符BCB也是取第2、3、5个字符。因为原来整个密码是回文的残缺串里的任何一段回文子序列都可以看成是原密码保留下来的部分。真正脱落掉的字符数量就是最少脱落数 原串长度 - 最长回文子序列长度这个公式是整个题目的核心。理解它比背代码重要得多。1.2 为什么不能用贪心非得用动态规划我见过不少初学者拿到这个题第一念头就是从左往右扫遇到不匹配的就删掉一个统计删除次数。这种思路在有些字符串上碰巧能过但本质上不对。举个例子字符串ABCA从左往右判断回文会很别扭因为第一个字符和最后一个字符不相等你根本不知道该删哪个。如果删掉A剩下BCA不是回文删掉B剩下ACA倒是回文了可你怎么知道该删B而不是删A呢贪心的困境就在于当两个端点不相等时当前这一步的“最优选择”无法通过局部信息判断必须依赖后面的字符情况。而动态规划之所以适合这个问题是因为它把“从某个区间里能拼出多长的回文子序列”这件事拆成了具有最优子结构的小问题长区间的最优解由短区间的最优解递推而来。短区间的答案是确定的长区间的答案就站得住。我第一次做这道题的时候其实也绕了一段弯路总觉得题目是在考字符串匹配后来才意识到这根本是一个典型的区间DP。明白这一点之后代码反而不长了核心逻辑十几个小时就讲得完但状态设计和递推顺序想明白比代码本身值钱。2. 动态规划模型的详细推导2.1 状态定义dp[i][j] 到底表示什么做动态规划第一步永远是定义状态。对于这道题自然的选择是定义二维数组dp[i][j] 字符串 s[i] 到 s[j] 这个闭区间内最长回文子序列的长度特别注意这里的 i 和 j 是下标且约定 i j。当 i j 时表示空区间dp 值为 0当 i j 时区间里只有一个字符单个字符本身就是一个回文串长度为 1。定义完状态之后就可以思考转移了。假设我现在要求 dp[i][j]那么分两种情况情况一s[i] s[j]这个时候两端的字符相等它们天然可以形成回文串的最外层。相当于我们取这个区间的首尾两个字符再把里面s[i1]到s[j-1]的最长回文子序列包在中间长度就是dp[i][j] dp[i1][j-1] 2情况二s[i] ! s[j]两端字符不相等它们不可能同时出现在一个回文子序列的首尾。那这个区间的最长回文子序列要么在去掉左边字符的区间[i1, j]里要么在去掉右边字符的区间[i, j-1]里。哪个更长取哪个dp[i][j] max(dp[i1][j], dp[i][j-1])这就是全部的状态转移逻辑简单到让人觉得不太敢相信。但正是这个简洁的转移方程把整个问题彻底解决了。2.2 为什么答案等于 n - dp[0][n-1]理解了最长回文子序列之后还要把答案和这个问题串起来为什么最少的脱落数就是原长度减去最长回文子序列长度而不是别的什么可以从两个方向理解。先朝一个方向想假设我在残缺串中找到了一个长度为 L 的回文子序列那么我可以认为原密码中至少有这么 L 个字符是保留到现在并且“天然对称”的。剩下 n - L 个字符都是回文结构之外的东西——要么本来就是原密码中左右不对称、需要靠互相配对才能成回文的字符但因为配对的那一半脱落了所以这一半也成为多余要么就是普通字符在脱落过程中打乱了顺序。无论如何要让残留串恢复到回文状态这 n - L 个字符都得从回文结构里剔除出去或者说它们对应的原密码字符已经掉光了所以最少脱落数不会小于 n - L。再朝另一个方向想如果我们什么都不做直接认为“原来整串都掉光了只剩这 n 个字符”那这 n 个字符并不一定是回文所以它们中必然有一部分不是原密码对称结构中的成员。如果原密码真的有 n - L 个字符脱落就意味着原本每一个脱落的字符都能在残留串里找到一个“失去配偶”的回文伴侣——这种配对关系恰恰是回文子序列所描述的。最终结论就是min_removed n - longest_palindromic_subsequence_length这个转化核心要记牢很多类似的字符串复原题最后都归结到最长回文子序列或最长公共子序列上。2.3 计算方向为什么 i 要从大到小遍历写区间DP的时候初学者最容易栽跟头的地方是循环的顺序。看转移方程dp[i][j]依赖dp[i1][j-1]区间缩小左下角dp[i][j]依赖dp[i1][j]区间左端右移一位dp[i][j]依赖dp[i][j-1]区间右端左移一位也就是说要计算dp[i][j]需要先知道那些区间长度更短的子问题的答案。所以我们可以按区间长度从短到长来填表或者等价地让 i 从大到小遍历、j 从小到大遍历。如果 i 从小到大、j 也从大到小那就完蛋了——你要算dp[i1][j]的时候它可能还没被算出来拿到的全是0结果自然全错。这不是算法问题是填表顺序问题。我建议新手养成一个习惯写区间DP之前先在纸上画一个二维表格把依赖关系画成箭头看看每个格子的数据到底从哪些格子来然后顺着依赖方向去遍历。画完你就明白为什么这里 i 的循环要for(i n-1; i 0; i--)j 的循环要for(j i1; j n; j)。3. C语言完整代码实现与逐步讲解3.1 最直观的二维DP写法下面给出一个基础的、不用任何优化的C语言实现这段代码可以直接复制到编译器里跑#include stdio.h #include string.h #define MAXN 1005 int dp[MAXN][MAXN]; char s[MAXN]; int max(int a, int b) { return a b ? a : b; } int main() { // 注意用 fgets 读字符串避免末尾换行符混入 if (fgets(s, MAXN, stdin) NULL) { return 0; } // 去掉 fgets 可能读进来的换行符 int len strlen(s); while (len 0 (s[len-1] \n || s[len-1] \r)) { s[len-1] \0; len--; } int n len; // 初始化长度为1的子区间dp值为1 for (int i 0; i n; i) { dp[i][i] 1; } // 按区间长度从短到长递推 // i 从大到小j 从小到大 for (int i n - 1; i 0; i--) { for (int j i 1; j n; j) { if (s[i] s[j]) { dp[i][j] dp[i1][j-1] 2; } else { dp[i][j] max(dp[i1][j], dp[i][j-1]); } } } int lps dp[0][n-1]; // 最长回文子序列长度 int answer n - lps; // 最少脱落数 printf(%d\n, answer); return 0; }不要小看这段代码它包含了几个容易出错的关键细节。细节一读字符串。fgets会把换行符也读进来如果你不处理s的最后会多个\n导致字符串长度多1而且\n还会参与比较直接影响结果。我一向建议直接用fgets读取然后手动剥掉末尾的换行。如果你用的是scanf(%s, s)其实是不会遇到这个问题的因为%s会自动跳过空白符但fgets更安全能处理包含空格的情况。细节二初始化。dp[i][i] 1是必须的因为长度为1的区间就是最基础的回文串。不初始化的话从dp[i1][j-1]递推时当区间长度为2时dp[i1][j-1]其实是dp[i1][i]这是我们约定为0的空区间所以没问题但长度为1的格子如果没有初始化为1整个递推结果都会少算。我见过有人把dp[i][i]漏掉结果一跑全是0排查半天才发现是这个原因。细节三i 和 j 的边界。内层循环j从i1开始避免了处理i j的空区间也避免和dp[i][i]重复初始化。如果你写成j i开始那dp[i][i]可能会被dp[i1][i-1]这种非法索引覆盖很危险。3.2 用 LCS最长公共子序列思路来解第二种常见解法是把密码脱落问题转换成求原串和逆序串的最长公共子序列。方法很简单把原串s反转成t然后求s和t的 LCS 长度这个长度恰好就是原串的最长回文子序列长度。为什么成立因为回文串反转之后和原来一样。如果s里有一段回文子序列那么它在反转后的t里必然也以相同顺序出现反转后顺序恰好相反但作为回文子序列它的字符顺序在正反两个串里是镜像对称的所以 LCS 至少等于最长回文子序列。反过来s和t的任何公共子序列因为t是s的反转实际上就对应了原串里一个从前向后取、再从后向前镜像取的回文序列。两边互相包含所以相等。LCS 版本的代码也很经典用二维dp[i][j]表示s的前 i 个字符和t的前 j 个字符的 LCS 长度#include stdio.h #include string.h #define MAXN 1005 int dp[MAXN][MAXN]; char s[MAXN], t[MAXN]; int max(int a, int b) { return a b ? a : b; } int main() { if (fgets(s, MAXN, stdin) NULL) return 0; int n strlen(s); while (n 0 (s[n-1] \n || s[n-1] \r)) { s[n-1] \0; n--; } // 构造逆序串 for (int i 0; i n; i) { t[i] s[n-1-i]; } t[n] \0; // LCS 动态规划 for (int i 1; i n; i) { for (int j 1; j n; j) { if (s[i-1] t[j-1]) { dp[i][j] dp[i-1][j-1] 1; } else { dp[i][j] max(dp[i-1][j], dp[i][j-1]); } } } printf(%d\n, n - dp[n][n]); return 0; }两种解法做的是同一件事但理解的角度不同区间DP是从回文结构本身出发LCS 是从“回文串反转不变”的性质出发。实际做题时用哪一种都可以面试时能给面试官讲清楚其中一种并分析复杂度就够了。不过我个人更推荐把区间DP的思路吃透因为它在后续处理“最长回文子串”或“最少插入字符构造回文串”等变体题时可以直接迁移。4. 复杂度分析与空间优化方案4.1 时间和空间到底是多少先看二维DP版本。两个循环都嵌套遍历一遍所有区间时间复杂度是 O(n²)。空间上dp数组是 n×n 的二维数组空间复杂度也是 O(n²)。当 n 在 1000 左右时1000×1000 的 int 数组占用约 4MB完全没压力。但当 n 达到 5000 甚至 10000 时5000×5000 的 int 就是 100MB很多OJ会直接内存超限。所以空间优化在实际比赛中不是可选项是必选项。注意如果题目给了明确的数据范围比如 n 1000那直接用二维数组就行代码简洁、不易出错。只有当 n 很大时才需要滚动数组。4.2 滚动数组把空间压到 O(n)观察区间DP的转移方程每次更新dp[i][j]时依赖的是dp[i1][j-1]下一行的左边一列dp[i1][j]下一行的同一列dp[i][j-1]当前行的左边一列可以看到当前行只依赖下一行的数据。换句话说我需要保留的只是“下一行”这个一维数组而不是整个二维表格。实现时用两个一维数组轮流使用也就是滚动数组。#include stdio.h #include string.h #define MAXN 5005 char s[MAXN]; int dp[2][MAXN]; // 滚动数组 int max(int a, int b) { return a b ? a : b; } int main() { if (fgets(s, MAXN, stdin) NULL) return 0; int n strlen(s); while (n 0 (s[n-1] \n || s[n-1] \r)) { s[n-1] \0; n--; } int cur 0, nxt 1; // 逆序枚举 i for (int i n - 1; i 0; i--) { // 当前这一行从 i 开始处理 dp[cur][i] 1; // 长度为1的子区间 for (int j i 1; j n; j) { if (s[i] s[j]) { dp[cur][j] dp[nxt][j-1] 2; } else { dp[cur][j] max(dp[nxt][j], dp[cur][j-1]); } } // 交换当前行和下一行 int tmp cur; cur nxt; nxt tmp; } // 循环结束时答案在上一轮 nxt 数组里需要理清楚 // 更稳妥的做法在循环内记录答案 printf(%d\n, n - dp[nxt][n-1]); return 0; }这个滚动数组版本有几个容易踩坑的地方我详细说一下。坑一每次外层循环开始dp[cur][i] 1必须设置。因为内层循环从j i 1开始dp[i][i]不会在循环体内被赋值如果不手动初始化他就沿用上一轮残留的旧数据结果完全错误。坑二注意dp[cur][j-1]是当前行刚更新的值而dp[nxt][j]和dp[nxt][j-1]是上一行的值。很多同学写滚动数组时搞混 cur 和 nxt 的角色然后要么越界、要么数据交叉污染。我的建议是在每个循环开头画一画当前这行和下一行的关系想清楚再写。坑三循环结束后答案到底在哪个数组里。因为外层循环每轮都会交换cur和nxt循环结束后的cur和nxt指向的行和逻辑上的“行”不是一回事。与其事后推理不如在每次内层循环结束、算出dp[cur][n-1]之后直接用变量把答案存下来。这样既直观也不容易错。滚动数组优化后的空间复杂度是 O(n)但时间复杂度仍然是 O(n²)因为递推的过程没有减少只是内存占用降低了。4.3 空间还能再省吗进一步优化对这道题来说滚动数组已经足够应对绝大多数数据范围。理论上还有一种优化思路把 int 数组改成 short 或 unsigned short如果 n 不超过 65535可以省一半空间。但这样做的实用性很低而且在某些平台上 short 的运算速度反而不如 int。我不建议为了省空间去折腾类型转换除非题目数据卡得非常紧。另一种思路是直接用一维数组加临时变量完全去掉二维滚动。实现上因为当前行dp[j]更新时需要同时使用“上一行的 dp[j]”和“上一行的 dp[j-1]”以及“当前行的 dp[j-1]”在更新的时候必须用一个临时变量把“上一行的 dp[j-1]”存下来否则被覆盖后就用不了了。代码会更绕除非面试官专门问否则我不推荐在日常练习中写这种过于紧凑的版本——它容易出错而且可读性差。从实际做题角度我建议先用二维版本确保思路正确再根据题目数据范围决定要不要换滚动数组。做题第一要义是正确第二才是优化。不要一上来就写滚动数组结果调了一个小时还找不出错。5. 常见问题与调试技巧实录5.1 字符串输入处理不当这个问题出现的频率出奇地高。很多人直接用scanf(%s, s)读但遇到字符串中间有空格的情况就会读错换成fgets之后又忘了末尾的换行符。我处理输入的习惯是如果题目明确是单串且不含空格用scanf(%s, s)最省事。如果可能包含空格用fgets(s, MAXN, stdin)读入然后手动去掉末尾的\n和\r。去掉末尾换行符的代码建议写成一个固定的小工具函数因为很多题都要用void strip_newline(char *s) { int len strlen(s); while (len 0 (s[len-1] \n || s[len-1] \r)) { s[--len] \0; } }5.2 数组越界与初始化遗漏二维DP版本中dp[i1][j-1]在j i1时访问的是dp[i1][i]这个位置虽然在常规循环中不会被显式赋值但因为它不在循环范围内值都是数组初始化后的0恰好代表空区间所以没问题。但如果你把dp定义成局部数组却不初始化那dp[i1][i]可能就是垃圾值。所以全局变量数组自动初始化为0的机制在这里很重要我习惯把dp和s都定义为全局变量省去手动memset的麻烦。如果非要用局部数组记得memset(dp, 0, sizeof(dp));5.3 循环方向写反导致答案错误这是区间DP里最典型的错误没有之一。代码看起来完全没毛病一跑样例也过了但对拍大数据时就会发现问题。我调试的时候有个笨但有效的办法把 dp 表打印出来。在循环结束后加一段打印代码把 dp 的前几行输出到终端手动核对几个关键位置。比如对于一个长度为5的字符串ABCBD你可以手动算一下dp[0][0] 1dp[0][1]A 和 B 不相等所以max(dp[1][1], dp[0][0]) max(1, 1) 1dp[0][2]A 和 C 不相等max(dp[1][2], dp[0][1]) max(1, 1) 1dp[1][3]B 和 B 相等dp[2][2] 2 3手动算几个值再和程序输出对照很快就能定位问题是出在递推逻辑还是初始化上。5.4 样例过了但提交后WA怎么办样例覆盖的路径太少经常出现“样例过了、提交全错”的情况。这时候我强烈建议自己构造几个边界测试空串或长度为1的字符串答案应该是0。整个串已经是回文答案应该是0。完全无重复字符的串比如abcdef最长回文子序列长度是1答案是 n-1。全是相同字符的串比如aaaaa最长回文子序列长度是 n答案是0。形如ab的字符串最长回文子序列长度是1答案是1。这些边界测试写成一个临时测试函数一条条跑能快速筛掉大部分逻辑错误。5.5 关于代码风格的两个建议第一max函数不要用宏定义#define max(a,b) ((a)(b)?(a):(b))因为宏在参数带副作用时会出问题比如max(dp[i], j--)这种写法会病态地展开。用函数就行编译器会内联优化性能没有差别。第二全局数组的尺寸不要抠得太死。题目说 n 1000你开MAXN 1005没问题但养成开大一点的MAXN 1005或1010的习惯能避免一些边界情况下的越界。如果题目说 n 100000那就必须用滚动数组了因为 100000×100000 的二维数组根本无法分配。6. 变形题目与扩展思考6.1 最少插入字符构造回文串有一道很常见的变体题给定一个字符串允许你往任意位置插入字符问最少插入多少个字符能让整个串变成回文。答案恰好也是n - 最长回文子序列长度。为什么因为原串中那个最长的回文子序列已经可以保持不动剩下的 n - L 个字符每个都需要在相对位置补一个配对字符才能让整个串变成回文。所以最少插入数和最少删除数在数值上是一样的虽然操作方向不同但底层决策逻辑完全一致。碰到这道题的时候直接套用密码脱落问题的代码就可以。6.2 最长回文子串连续回文和子序列回文的区别很多初学者会把“最长回文子序列”和“最长回文子串”搞混。子串必须是连续的比如ABCBD里的最长回文子串是BCB长度为3而最长回文子序列可以是ABCBA长度5因为A、B、C、B、A分别取自原串的第0、1、2、3、4个字符吗不对ABCBD里没有最后一个A所以最长回文子序列其实是BCB或ABA长度都是3。这里举例子要小心。举例BBABCBCAB的最长回文子序列是BACBCAB或BBCAB B长度7但最长回文子串可能是BAB、BCB长度3。两者的求解方法也完全不同最长回文子序列用区间DP子序列允许跳着取。最长回文子串可以用中心扩展法O(n²) 时间O(1) 空间也可以用 Manacher 算法O(n) 时间。如果你在面试里把这两个概念说混了面试官大概率会追问场面会非常尴尬。建议把这两个问题的代码都写一遍彻底分清。6.3 LCS 解法的拔高理解用 LCS 解密码脱落问题本质上利用了“原串和逆序串的公共子序列一定对应着原串中的一个回文子序列”这个性质。这个性质理解透了对之后做编辑距离、最长公共子串等题目都有帮助。举个例子s AGBCBA它的逆序是ABC BGA其实你要求的是两个串的最长公共子序列。s和逆序串的公共子序列AGB在s里是从左向右读在逆序串里是从右向左读所以这两个方向组合起来确实对应了原串里的回文序列。这个思想比单纯的 DP 代码更有迁移价值我在面试中讲这道题的时候经常从 LCS 入手因为它能直观地体现“回文”和“公共子序列”之间深刻的联系。6.4 如果题目要求输出脱落的字符或原密码有时候题目会从“求最少脱落数量”升级成“输出一种可能的原密码”。这时候光靠 dp 数组的数值不够还需要记录每个状态是从哪个转移得到的或者在 dp 结束后用回溯法重构。回溯的思路是从dp[0][n-1]往回走比较s[i]和s[j]如果相等说明这两个字符组成了回文首尾输出s[i]继续追踪(i1, j-1)。如果不相等判断dp[i][j]等于dp[i1][j]还是dp[i][j-1]往值更大的那个方向回溯。重构出来的字符序列最外层到最内层依次放入结果字符串的两端最后拼起来就是一个可能的原密码。不过这类输出型题目容易在边界上翻车建议在代码里写出清晰的递归函数并且每次递归之前检查区间是否有效。7. 实践中的调试技巧与个人心得7.1 构造一个“对拍器”来验证正确性个人强烈建议在学习算法题时养成一个习惯写一个暴力解法做对拍。密码脱落问题可以写一个二进制枚举所有子序列的暴力程序对于长度不超过15的随机字符串判断每个子序列是否是回文然后求出最长长度。有了暴力程序当参照再跑随机数据对拍能在几秒内发现你的 DP 是否有问题。对拍器的思路是写一个brute_force()函数生成所有子序列用位运算枚举逐个判断回文。写一个solve()函数用 DP 计算。在主函数里生成随机小字符串分别调用两个函数对比结果。这种方法在海量随机数据下能非常高效地暴露逻辑错误比反复提交 OJ 快得多。我现在的习惯是很多题目写完 DP 之后第一件事不是提交而是先跑一分钟对拍。7.2 用笔在纸上走一遍执行流程区间DP的表格不像普通一维DP那么直观填表方向弄错的话看代码往往发现不了问题。我调试时会把一个长度为4或5的字符串的 dp 表完整地画出来把每个格子的计算过程标在旁边。比如对于字符串ABABdp[0][0] 1dp[0][1]A ! Bmax(dp[1][1], dp[0][0]) max(1, 1) 1dp[0][2]A Adp[1][1] 2 3继续往下填最终dp[0][3]应该是3ABA或BAB答案就是4 - 3 1。手动算过一张表之后你对状态的定义、转移方程的计算方向都会有非常直观的感受以后再遇到类似的区间DP题就能比较自然地想到怎么定义状态和转移。7.3 关于动态规划的“无后效性”问题稍微聊深一点。这道题之所以能用动态规划是因为它满足无后效性dp[i][j]一旦算出来就只代表区间[i, j]的最长回文子序列长度不关心这个子序列具体是哪几个字符也不需要知道区间外面的情况。外层区间的计算只依赖内层区间的结果不会因为外层有什么额外条件而改变内层的值。这是动态规划能够奏效的根本原因。如果你在做一道题时感觉状态定义出来了但转移时总需要考虑“之前选过哪些字符”之类的额外信息那大概率是状态设计得不够好需要增加维度或换一种状态描述。密码脱落问题是一个很好的教学案例状态只跟区间有关不需要记录任何选择历史所以推导会非常干净。7.4 什么时候用密码脱落问题这种写法最后聊一聊代码风格。这类经典DP题其实没有太多花哨的优化空间代码主要看三点正确性、清晰度、可维护性。我见过有的同学为了炫技把循环写得很紧凑例如把if/else压缩成三目运算符嵌套代码长度很短但可读性极差。我个人的建议是在比赛中怎么写都无所谓能AC就是胜利但在平时的学习代码和面试代码中追求清晰比追求简短重要得多。面试时如果写这道题我会刻意把状态定义、初始化、三重递推逻辑用注释标清楚这样即使面试官不熟悉这道题也能顺畅地跟上你的思路。代码除了跑出正确答案之外还承担着沟通的作用这一点常常被忽略。以上是我在做“密码脱落问题”时积累的完整思路和实操经验从状态设计到代码实现再到空间优化和调试技巧希望能帮正在学习动态规划的你少走一些弯路。 
长河君 · 2026/9/10 19:10:22 · 阅读 1.2k 密码脱落问题与最长回文子序列：动态规划核心思路详解
1. 问题描述与核心思路拆解1.1 先把这个题目的场景讲清楚“密码脱落问题”不是一道生僻的偏题怪题恰恰相反它是动态规划入门阶段非常有代表性的经典题在很多学校的OJ、课程设计和面试题库里都能看到它的身影。题目本身借了一个考古背景一串由字母或数字组成的密码原本是一个回文串但因为年代久远部分字符脱落了只剩下现在这一串残缺的序列。现在要根据剩下的序列算出最少脱落了多少个字符。很多刚接触这个题的同学第一反应是那我怎么知道原来长什么样确实题目没有直接给出原密码只给了残缺序列。但细想一下会发现问题的关键不是复原原字符串而是找残留串里的信息——如果某一段字符原本就是回文的那这一段就“没怎么脱落”脱落得越多剩下的东西就越不“回文”。所以这个问题的本质是求给定字符串的最长回文子序列长度。什么叫“回文子序列”简单说从原串里挑出一部分字符保持它们在原串中的相对顺序不变拼出来的新串如果是回文从前往后读和从后往前读一样那它就是原串的一个回文子序列。注意子序列和子串不一样子串必须是连续的子序列允许跳着取。比如ABCBD的子序列ABD就不是回文但ABA是取第1、2、4个字符BCB也是取第2、3、5个字符。因为原来整个密码是回文的残缺串里的任何一段回文子序列都可以看成是原密码保留下来的部分。真正脱落掉的字符数量就是最少脱落数 原串长度 - 最长回文子序列长度这个公式是整个题目的核心。理解它比背代码重要得多。1.2 为什么不能用贪心非得用动态规划我见过不少初学者拿到这个题第一念头就是从左往右扫遇到不匹配的就删掉一个统计删除次数。这种思路在有些字符串上碰巧能过但本质上不对。举个例子字符串ABCA从左往右判断回文会很别扭因为第一个字符和最后一个字符不相等你根本不知道该删哪个。如果删掉A剩下BCA不是回文删掉B剩下ACA倒是回文了可你怎么知道该删B而不是删A呢贪心的困境就在于当两个端点不相等时当前这一步的“最优选择”无法通过局部信息判断必须依赖后面的字符情况。而动态规划之所以适合这个问题是因为它把“从某个区间里能拼出多长的回文子序列”这件事拆成了具有最优子结构的小问题长区间的最优解由短区间的最优解递推而来。短区间的答案是确定的长区间的答案就站得住。我第一次做这道题的时候其实也绕了一段弯路总觉得题目是在考字符串匹配后来才意识到这根本是一个典型的区间DP。明白这一点之后代码反而不长了核心逻辑十几个小时就讲得完但状态设计和递推顺序想明白比代码本身值钱。2. 动态规划模型的详细推导2.1 状态定义dp[i][j] 到底表示什么做动态规划第一步永远是定义状态。对于这道题自然的选择是定义二维数组dp[i][j] 字符串 s[i] 到 s[j] 这个闭区间内最长回文子序列的长度特别注意这里的 i 和 j 是下标且约定 i j。当 i j 时表示空区间dp 值为 0当 i j 时区间里只有一个字符单个字符本身就是一个回文串长度为 1。定义完状态之后就可以思考转移了。假设我现在要求 dp[i][j]那么分两种情况情况一s[i] s[j]这个时候两端的字符相等它们天然可以形成回文串的最外层。相当于我们取这个区间的首尾两个字符再把里面s[i1]到s[j-1]的最长回文子序列包在中间长度就是dp[i][j] dp[i1][j-1] 2情况二s[i] ! s[j]两端字符不相等它们不可能同时出现在一个回文子序列的首尾。那这个区间的最长回文子序列要么在去掉左边字符的区间[i1, j]里要么在去掉右边字符的区间[i, j-1]里。哪个更长取哪个dp[i][j] max(dp[i1][j], dp[i][j-1])这就是全部的状态转移逻辑简单到让人觉得不太敢相信。但正是这个简洁的转移方程把整个问题彻底解决了。2.2 为什么答案等于 n - dp[0][n-1]理解了最长回文子序列之后还要把答案和这个问题串起来为什么最少的脱落数就是原长度减去最长回文子序列长度而不是别的什么可以从两个方向理解。先朝一个方向想假设我在残缺串中找到了一个长度为 L 的回文子序列那么我可以认为原密码中至少有这么 L 个字符是保留到现在并且“天然对称”的。剩下 n - L 个字符都是回文结构之外的东西——要么本来就是原密码中左右不对称、需要靠互相配对才能成回文的字符但因为配对的那一半脱落了所以这一半也成为多余要么就是普通字符在脱落过程中打乱了顺序。无论如何要让残留串恢复到回文状态这 n - L 个字符都得从回文结构里剔除出去或者说它们对应的原密码字符已经掉光了所以最少脱落数不会小于 n - L。再朝另一个方向想如果我们什么都不做直接认为“原来整串都掉光了只剩这 n 个字符”那这 n 个字符并不一定是回文所以它们中必然有一部分不是原密码对称结构中的成员。如果原密码真的有 n - L 个字符脱落就意味着原本每一个脱落的字符都能在残留串里找到一个“失去配偶”的回文伴侣——这种配对关系恰恰是回文子序列所描述的。最终结论就是min_removed n - longest_palindromic_subsequence_length这个转化核心要记牢很多类似的字符串复原题最后都归结到最长回文子序列或最长公共子序列上。2.3 计算方向为什么 i 要从大到小遍历写区间DP的时候初学者最容易栽跟头的地方是循环的顺序。看转移方程dp[i][j]依赖dp[i1][j-1]区间缩小左下角dp[i][j]依赖dp[i1][j]区间左端右移一位dp[i][j]依赖dp[i][j-1]区间右端左移一位也就是说要计算dp[i][j]需要先知道那些区间长度更短的子问题的答案。所以我们可以按区间长度从短到长来填表或者等价地让 i 从大到小遍历、j 从小到大遍历。如果 i 从小到大、j 也从大到小那就完蛋了——你要算dp[i1][j]的时候它可能还没被算出来拿到的全是0结果自然全错。这不是算法问题是填表顺序问题。我建议新手养成一个习惯写区间DP之前先在纸上画一个二维表格把依赖关系画成箭头看看每个格子的数据到底从哪些格子来然后顺着依赖方向去遍历。画完你就明白为什么这里 i 的循环要for(i n-1; i 0; i--)j 的循环要for(j i1; j n; j)。3. C语言完整代码实现与逐步讲解3.1 最直观的二维DP写法下面给出一个基础的、不用任何优化的C语言实现这段代码可以直接复制到编译器里跑#include stdio.h #include string.h #define MAXN 1005 int dp[MAXN][MAXN]; char s[MAXN]; int max(int a, int b) { return a b ? a : b; } int main() { // 注意用 fgets 读字符串避免末尾换行符混入 if (fgets(s, MAXN, stdin) NULL) { return 0; } // 去掉 fgets 可能读进来的换行符 int len strlen(s); while (len 0 (s[len-1] \n || s[len-1] \r)) { s[len-1] \0; len--; } int n len; // 初始化长度为1的子区间dp值为1 for (int i 0; i n; i) { dp[i][i] 1; } // 按区间长度从短到长递推 // i 从大到小j 从小到大 for (int i n - 1; i 0; i--) { for (int j i 1; j n; j) { if (s[i] s[j]) { dp[i][j] dp[i1][j-1] 2; } else { dp[i][j] max(dp[i1][j], dp[i][j-1]); } } } int lps dp[0][n-1]; // 最长回文子序列长度 int answer n - lps; // 最少脱落数 printf(%d\n, answer); return 0; }不要小看这段代码它包含了几个容易出错的关键细节。细节一读字符串。fgets会把换行符也读进来如果你不处理s的最后会多个\n导致字符串长度多1而且\n还会参与比较直接影响结果。我一向建议直接用fgets读取然后手动剥掉末尾的换行。如果你用的是scanf(%s, s)其实是不会遇到这个问题的因为%s会自动跳过空白符但fgets更安全能处理包含空格的情况。细节二初始化。dp[i][i] 1是必须的因为长度为1的区间就是最基础的回文串。不初始化的话从dp[i1][j-1]递推时当区间长度为2时dp[i1][j-1]其实是dp[i1][i]这是我们约定为0的空区间所以没问题但长度为1的格子如果没有初始化为1整个递推结果都会少算。我见过有人把dp[i][i]漏掉结果一跑全是0排查半天才发现是这个原因。细节三i 和 j 的边界。内层循环j从i1开始避免了处理i j的空区间也避免和dp[i][i]重复初始化。如果你写成j i开始那dp[i][i]可能会被dp[i1][i-1]这种非法索引覆盖很危险。3.2 用 LCS最长公共子序列思路来解第二种常见解法是把密码脱落问题转换成求原串和逆序串的最长公共子序列。方法很简单把原串s反转成t然后求s和t的 LCS 长度这个长度恰好就是原串的最长回文子序列长度。为什么成立因为回文串反转之后和原来一样。如果s里有一段回文子序列那么它在反转后的t里必然也以相同顺序出现反转后顺序恰好相反但作为回文子序列它的字符顺序在正反两个串里是镜像对称的所以 LCS 至少等于最长回文子序列。反过来s和t的任何公共子序列因为t是s的反转实际上就对应了原串里一个从前向后取、再从后向前镜像取的回文序列。两边互相包含所以相等。LCS 版本的代码也很经典用二维dp[i][j]表示s的前 i 个字符和t的前 j 个字符的 LCS 长度#include stdio.h #include string.h #define MAXN 1005 int dp[MAXN][MAXN]; char s[MAXN], t[MAXN]; int max(int a, int b) { return a b ? a : b; } int main() { if (fgets(s, MAXN, stdin) NULL) return 0; int n strlen(s); while (n 0 (s[n-1] \n || s[n-1] \r)) { s[n-1] \0; n--; } // 构造逆序串 for (int i 0; i n; i) { t[i] s[n-1-i]; } t[n] \0; // LCS 动态规划 for (int i 1; i n; i) { for (int j 1; j n; j) { if (s[i-1] t[j-1]) { dp[i][j] dp[i-1][j-1] 1; } else { dp[i][j] max(dp[i-1][j], dp[i][j-1]); } } } printf(%d\n, n - dp[n][n]); return 0; }两种解法做的是同一件事但理解的角度不同区间DP是从回文结构本身出发LCS 是从“回文串反转不变”的性质出发。实际做题时用哪一种都可以面试时能给面试官讲清楚其中一种并分析复杂度就够了。不过我个人更推荐把区间DP的思路吃透因为它在后续处理“最长回文子串”或“最少插入字符构造回文串”等变体题时可以直接迁移。4. 复杂度分析与空间优化方案4.1 时间和空间到底是多少先看二维DP版本。两个循环都嵌套遍历一遍所有区间时间复杂度是 O(n²)。空间上dp数组是 n×n 的二维数组空间复杂度也是 O(n²)。当 n 在 1000 左右时1000×1000 的 int 数组占用约 4MB完全没压力。但当 n 达到 5000 甚至 10000 时5000×5000 的 int 就是 100MB很多OJ会直接内存超限。所以空间优化在实际比赛中不是可选项是必选项。注意如果题目给了明确的数据范围比如 n 1000那直接用二维数组就行代码简洁、不易出错。只有当 n 很大时才需要滚动数组。4.2 滚动数组把空间压到 O(n)观察区间DP的转移方程每次更新dp[i][j]时依赖的是dp[i1][j-1]下一行的左边一列dp[i1][j]下一行的同一列dp[i][j-1]当前行的左边一列可以看到当前行只依赖下一行的数据。换句话说我需要保留的只是“下一行”这个一维数组而不是整个二维表格。实现时用两个一维数组轮流使用也就是滚动数组。#include stdio.h #include string.h #define MAXN 5005 char s[MAXN]; int dp[2][MAXN]; // 滚动数组 int max(int a, int b) { return a b ? a : b; } int main() { if (fgets(s, MAXN, stdin) NULL) return 0; int n strlen(s); while (n 0 (s[n-1] \n || s[n-1] \r)) { s[n-1] \0; n--; } int cur 0, nxt 1; // 逆序枚举 i for (int i n - 1; i 0; i--) { // 当前这一行从 i 开始处理 dp[cur][i] 1; // 长度为1的子区间 for (int j i 1; j n; j) { if (s[i] s[j]) { dp[cur][j] dp[nxt][j-1] 2; } else { dp[cur][j] max(dp[nxt][j], dp[cur][j-1]); } } // 交换当前行和下一行 int tmp cur; cur nxt; nxt tmp; } // 循环结束时答案在上一轮 nxt 数组里需要理清楚 // 更稳妥的做法在循环内记录答案 printf(%d\n, n - dp[nxt][n-1]); return 0; }这个滚动数组版本有几个容易踩坑的地方我详细说一下。坑一每次外层循环开始dp[cur][i] 1必须设置。因为内层循环从j i 1开始dp[i][i]不会在循环体内被赋值如果不手动初始化他就沿用上一轮残留的旧数据结果完全错误。坑二注意dp[cur][j-1]是当前行刚更新的值而dp[nxt][j]和dp[nxt][j-1]是上一行的值。很多同学写滚动数组时搞混 cur 和 nxt 的角色然后要么越界、要么数据交叉污染。我的建议是在每个循环开头画一画当前这行和下一行的关系想清楚再写。坑三循环结束后答案到底在哪个数组里。因为外层循环每轮都会交换cur和nxt循环结束后的cur和nxt指向的行和逻辑上的“行”不是一回事。与其事后推理不如在每次内层循环结束、算出dp[cur][n-1]之后直接用变量把答案存下来。这样既直观也不容易错。滚动数组优化后的空间复杂度是 O(n)但时间复杂度仍然是 O(n²)因为递推的过程没有减少只是内存占用降低了。4.3 空间还能再省吗进一步优化对这道题来说滚动数组已经足够应对绝大多数数据范围。理论上还有一种优化思路把 int 数组改成 short 或 unsigned short如果 n 不超过 65535可以省一半空间。但这样做的实用性很低而且在某些平台上 short 的运算速度反而不如 int。我不建议为了省空间去折腾类型转换除非题目数据卡得非常紧。另一种思路是直接用一维数组加临时变量完全去掉二维滚动。实现上因为当前行dp[j]更新时需要同时使用“上一行的 dp[j]”和“上一行的 dp[j-1]”以及“当前行的 dp[j-1]”在更新的时候必须用一个临时变量把“上一行的 dp[j-1]”存下来否则被覆盖后就用不了了。代码会更绕除非面试官专门问否则我不推荐在日常练习中写这种过于紧凑的版本——它容易出错而且可读性差。从实际做题角度我建议先用二维版本确保思路正确再根据题目数据范围决定要不要换滚动数组。做题第一要义是正确第二才是优化。不要一上来就写滚动数组结果调了一个小时还找不出错。5. 常见问题与调试技巧实录5.1 字符串输入处理不当这个问题出现的频率出奇地高。很多人直接用scanf(%s, s)读但遇到字符串中间有空格的情况就会读错换成fgets之后又忘了末尾的换行符。我处理输入的习惯是如果题目明确是单串且不含空格用scanf(%s, s)最省事。如果可能包含空格用fgets(s, MAXN, stdin)读入然后手动去掉末尾的\n和\r。去掉末尾换行符的代码建议写成一个固定的小工具函数因为很多题都要用void strip_newline(char *s) { int len strlen(s); while (len 0 (s[len-1] \n || s[len-1] \r)) { s[--len] \0; } }5.2 数组越界与初始化遗漏二维DP版本中dp[i1][j-1]在j i1时访问的是dp[i1][i]这个位置虽然在常规循环中不会被显式赋值但因为它不在循环范围内值都是数组初始化后的0恰好代表空区间所以没问题。但如果你把dp定义成局部数组却不初始化那dp[i1][i]可能就是垃圾值。所以全局变量数组自动初始化为0的机制在这里很重要我习惯把dp和s都定义为全局变量省去手动memset的麻烦。如果非要用局部数组记得memset(dp, 0, sizeof(dp));5.3 循环方向写反导致答案错误这是区间DP里最典型的错误没有之一。代码看起来完全没毛病一跑样例也过了但对拍大数据时就会发现问题。我调试的时候有个笨但有效的办法把 dp 表打印出来。在循环结束后加一段打印代码把 dp 的前几行输出到终端手动核对几个关键位置。比如对于一个长度为5的字符串ABCBD你可以手动算一下dp[0][0] 1dp[0][1]A 和 B 不相等所以max(dp[1][1], dp[0][0]) max(1, 1) 1dp[0][2]A 和 C 不相等max(dp[1][2], dp[0][1]) max(1, 1) 1dp[1][3]B 和 B 相等dp[2][2] 2 3手动算几个值再和程序输出对照很快就能定位问题是出在递推逻辑还是初始化上。5.4 样例过了但提交后WA怎么办样例覆盖的路径太少经常出现“样例过了、提交全错”的情况。这时候我强烈建议自己构造几个边界测试空串或长度为1的字符串答案应该是0。整个串已经是回文答案应该是0。完全无重复字符的串比如abcdef最长回文子序列长度是1答案是 n-1。全是相同字符的串比如aaaaa最长回文子序列长度是 n答案是0。形如ab的字符串最长回文子序列长度是1答案是1。这些边界测试写成一个临时测试函数一条条跑能快速筛掉大部分逻辑错误。5.5 关于代码风格的两个建议第一max函数不要用宏定义#define max(a,b) ((a)(b)?(a):(b))因为宏在参数带副作用时会出问题比如max(dp[i], j--)这种写法会病态地展开。用函数就行编译器会内联优化性能没有差别。第二全局数组的尺寸不要抠得太死。题目说 n 1000你开MAXN 1005没问题但养成开大一点的MAXN 1005或1010的习惯能避免一些边界情况下的越界。如果题目说 n 100000那就必须用滚动数组了因为 100000×100000 的二维数组根本无法分配。6. 变形题目与扩展思考6.1 最少插入字符构造回文串有一道很常见的变体题给定一个字符串允许你往任意位置插入字符问最少插入多少个字符能让整个串变成回文。答案恰好也是n - 最长回文子序列长度。为什么因为原串中那个最长的回文子序列已经可以保持不动剩下的 n - L 个字符每个都需要在相对位置补一个配对字符才能让整个串变成回文。所以最少插入数和最少删除数在数值上是一样的虽然操作方向不同但底层决策逻辑完全一致。碰到这道题的时候直接套用密码脱落问题的代码就可以。6.2 最长回文子串连续回文和子序列回文的区别很多初学者会把“最长回文子序列”和“最长回文子串”搞混。子串必须是连续的比如ABCBD里的最长回文子串是BCB长度为3而最长回文子序列可以是ABCBA长度5因为A、B、C、B、A分别取自原串的第0、1、2、3、4个字符吗不对ABCBD里没有最后一个A所以最长回文子序列其实是BCB或ABA长度都是3。这里举例子要小心。举例BBABCBCAB的最长回文子序列是BACBCAB或BBCAB B长度7但最长回文子串可能是BAB、BCB长度3。两者的求解方法也完全不同最长回文子序列用区间DP子序列允许跳着取。最长回文子串可以用中心扩展法O(n²) 时间O(1) 空间也可以用 Manacher 算法O(n) 时间。如果你在面试里把这两个概念说混了面试官大概率会追问场面会非常尴尬。建议把这两个问题的代码都写一遍彻底分清。6.3 LCS 解法的拔高理解用 LCS 解密码脱落问题本质上利用了“原串和逆序串的公共子序列一定对应着原串中的一个回文子序列”这个性质。这个性质理解透了对之后做编辑距离、最长公共子串等题目都有帮助。举个例子s AGBCBA它的逆序是ABC BGA其实你要求的是两个串的最长公共子序列。s和逆序串的公共子序列AGB在s里是从左向右读在逆序串里是从右向左读所以这两个方向组合起来确实对应了原串里的回文序列。这个思想比单纯的 DP 代码更有迁移价值我在面试中讲这道题的时候经常从 LCS 入手因为它能直观地体现“回文”和“公共子序列”之间深刻的联系。6.4 如果题目要求输出脱落的字符或原密码有时候题目会从“求最少脱落数量”升级成“输出一种可能的原密码”。这时候光靠 dp 数组的数值不够还需要记录每个状态是从哪个转移得到的或者在 dp 结束后用回溯法重构。回溯的思路是从dp[0][n-1]往回走比较s[i]和s[j]如果相等说明这两个字符组成了回文首尾输出s[i]继续追踪(i1, j-1)。如果不相等判断dp[i][j]等于dp[i1][j]还是dp[i][j-1]往值更大的那个方向回溯。重构出来的字符序列最外层到最内层依次放入结果字符串的两端最后拼起来就是一个可能的原密码。不过这类输出型题目容易在边界上翻车建议在代码里写出清晰的递归函数并且每次递归之前检查区间是否有效。7. 实践中的调试技巧与个人心得7.1 构造一个“对拍器”来验证正确性个人强烈建议在学习算法题时养成一个习惯写一个暴力解法做对拍。密码脱落问题可以写一个二进制枚举所有子序列的暴力程序对于长度不超过15的随机字符串判断每个子序列是否是回文然后求出最长长度。有了暴力程序当参照再跑随机数据对拍能在几秒内发现你的 DP 是否有问题。对拍器的思路是写一个brute_force()函数生成所有子序列用位运算枚举逐个判断回文。写一个solve()函数用 DP 计算。在主函数里生成随机小字符串分别调用两个函数对比结果。这种方法在海量随机数据下能非常高效地暴露逻辑错误比反复提交 OJ 快得多。我现在的习惯是很多题目写完 DP 之后第一件事不是提交而是先跑一分钟对拍。7.2 用笔在纸上走一遍执行流程区间DP的表格不像普通一维DP那么直观填表方向弄错的话看代码往往发现不了问题。我调试时会把一个长度为4或5的字符串的 dp 表完整地画出来把每个格子的计算过程标在旁边。比如对于字符串ABABdp[0][0] 1dp[0][1]A ! Bmax(dp[1][1], dp[0][0]) max(1, 1) 1dp[0][2]A Adp[1][1] 2 3继续往下填最终dp[0][3]应该是3ABA或BAB答案就是4 - 3 1。手动算过一张表之后你对状态的定义、转移方程的计算方向都会有非常直观的感受以后再遇到类似的区间DP题就能比较自然地想到怎么定义状态和转移。7.3 关于动态规划的“无后效性”问题稍微聊深一点。这道题之所以能用动态规划是因为它满足无后效性dp[i][j]一旦算出来就只代表区间[i, j]的最长回文子序列长度不关心这个子序列具体是哪几个字符也不需要知道区间外面的情况。外层区间的计算只依赖内层区间的结果不会因为外层有什么额外条件而改变内层的值。这是动态规划能够奏效的根本原因。如果你在做一道题时感觉状态定义出来了但转移时总需要考虑“之前选过哪些字符”之类的额外信息那大概率是状态设计得不够好需要增加维度或换一种状态描述。密码脱落问题是一个很好的教学案例状态只跟区间有关不需要记录任何选择历史所以推导会非常干净。7.4 什么时候用密码脱落问题这种写法最后聊一聊代码风格。这类经典DP题其实没有太多花哨的优化空间代码主要看三点正确性、清晰度、可维护性。我见过有的同学为了炫技把循环写得很紧凑例如把if/else压缩成三目运算符嵌套代码长度很短但可读性极差。我个人的建议是在比赛中怎么写都无所谓能AC就是胜利但在平时的学习代码和面试代码中追求清晰比追求简短重要得多。面试时如果写这道题我会刻意把状态定义、初始化、三重递推逻辑用注释标清楚这样即使面试官不熟悉这道题也能顺畅地跟上你的思路。代码除了跑出正确答案之外还承担着沟通的作用这一点常常被忽略。以上是我在做“密码脱落问题”时积累的完整思路和实操经验从状态设计到代码实现再到空间优化和调试技巧希望能帮正在学习动态规划的你少走一些弯路。