 内找到你的“完美镜像“？》)
《字符串相亲记：如何在 O(n²) 内找到你的"完美镜像"？》
又名：最长回文子序列——一个让字符串"自我欣赏"的算法
一、引子：当字符串开始自恋
话说在字符串王国里，每个字符串都有一个终极梦想——成为回文。
什么叫回文？就是那种正着读、反着读都一样的字符串，比如"level"、"noon"、"上海自来水来自海上"（中文乱入）。
但不是每个字符串都能天生丽质。比如"bbbab"这个倒霉蛋，它想当回文，但中间那个'a'像个电灯泡一样杵在那里，破坏了整体的和谐感。
于是它想：能不能删几个字符，让我变成一个回文？
这就是我们今天的主角——最长回文子序列（Longest Palindromic Subsequence）。
二、什么是子序列？别急，先吃个汉堡
在讲算法之前，必须先搞清楚一个概念：子序列。
假设你有一个汉堡，配料依次是：[面包, 生菜, 牛肉, 番茄, 面包]。
子序列的意思是：你可以不吃某些配料，但剩下配料的顺序不能变。
比如你可以吃[面包, 牛肉, 面包]（中间的生菜和番茄扔了），这算一个子序列。
但你不能变成[牛肉, 面包, 生菜]，因为顺序乱了——这就不是子序列，而是打乱顺序的黑暗料理了。
回到"bbbab"，它的子序列有：
"bbb"（删掉最后一个'a'和最后一个'b'）"bbbb"（删掉那个碍眼的'a'）"bab"（精简约会版）
其中最长的回文子序列就是"bbbb"，长度为 4。
三、解法一：二维 DP——"填格子"的艺术
3.1 核心思想：区间 DP
我们定义dp[i][j]为：字符串s[i...j]这个区间内的最长回文子序列长度。
注意，这里的关键是区间。我们要解决一个大问题（整个字符串），先解决一堆小问题（所有小区间），然后用小问题的答案拼出大问题的答案。
3.2 状态转移：相爱相杀的两种命运
现在我们盯着区间s[i...j]的两端：
命运 A：两端的字符一见钟情
s[i] == s[j]比如s = "bbbab"，区间[0, 4]两端都是'b'。那太好了！这两个'b'可以手拉手加入回文队伍。
此时：dp[i][j] = dp[i+1][j-1] + 2
意思是：中间部分[i+1, j-1]能凑出多长的回文，再加上我们俩这 2 个字符。
命运 B：两端的字符相看两厌
s[i] != s[j]比如区间[0, 3]，两端是'b'和'a'，不匹配。那怎么办？
只能二选一：
- 要么去掉左边的
'b'，看[1, 3]能搞多长 - 要么去掉右边的
'a'，看[0, 2]能搞多长
取两者最大值：dp[i][j] = max(dp[i+1][j], dp[i][j-1])
3.3 代码登场
classSolution{publicintlongestPalindromeSubseq(Strings){intn=s.length();int[][]dp=newint[n][n];// 对角线初始化：单个字符本身就是回文，长度为1for(inti=0;i<n;i++)dp[i][i]=1;// i 从下到上遍历（为什么？因为 dp[i][j] 依赖 dp[i+1][...]）for(inti=n-1;i>=0;i--){for(intj=i+1;j<n;j++){if(s.charAt(i)==s.charAt(j)){dp[i][j]=dp[i+1][j-1]+2;}else{dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);}}}returndp[0][n-1];}}3.4 填表过程可视化
以"bbbab"为例，填完表长这样：
0(b) 1(b) 2(b) 3(a) 4(b) 0 [ 1 2 3 3 4 ] 1 [ - 1 2 2 3 ] 2 [ - - 1 1 3 ] 3 [ - - - 1 1 ] 4 [ - - - - 1 ]右上角dp[0][4] = 4，就是答案。
复杂度：时间 O(n²)，空间 O(n²)。优点是思路清晰，缺点是空间有点大——就像你租房租了个三居室，其实一个人睡就够了。
四、解法二：一维 DP——"断舍离"的空间优化
面试官看完后点点头：“能不能优化一下空间？”
你微微一笑：“可以，用滚动数组。”
4.1 核心观察
仔细看二维 DP 的状态转移，dp[i][j]只依赖于：
dp[i+1][j-1]（左下角）dp[i+1][j]（正下方）dp[i][j-1]（左边）
也就是说，第i行只依赖于第i+1行。那干嘛存整个二维数组？用一维数组就够了！
4.2 变量们的"变形记"
我们用dp[j]表示当前正在计算的第i行。
但问题来了：当我们更新dp[j]时，需要用到：
dp[j]的旧值（表示dp[i+1][j]）dp[j-1]的新值（表示dp[i][j-1]，刚刚算好的）dp[i+1][j-1]（左下角，这个最棘手）
前两个直接用数组就行，但左下角怎么办？用prev变量来保存！
classSolution{publicintlongestPalindromeSubseq(Strings){intn=s.length();int[]dp=newint[n];for(inti=n-1;i>=0;i--){dp[i]=1;// 对角线初始化intprev=0;// 保存 dp[i+1][j-1]for(intj=i+1;j<n;j++){inttemp=dp[j];// 先保存 dp[i+1][j] 的旧值if(s.charAt(i)==s.charAt(j)){dp[j]=prev+2;}else{dp[j]=Math.max(dp[j],dp[j-1]);}prev=temp;// 下一轮，dp[i+1][j] 就变成 dp[i+1][j-1] 了！}}returndp[n-1];}}4.3 三步走战略
temp = dp[j]：保存旧值（dp[i+1][j]）- 计算
dp[j]的新值（dp[i][j]） prev = temp：把旧值交给prev，下一轮它就是左下角了
这就像接力赛跑，prev是接力棒，一棒接一棒传下去。
复杂度：时间 O(n²)，空间 O(n)。从三居室搬到单间，生活照样精彩。
五、解法三：LCS 转化——“打不过就搬救兵”
面试官推了推眼镜：“还有别的思路吗？”
你胸有成竹：“有，转化为最长公共子序列问题。”
5.1 一个神奇的等式
最长回文子序列 = 原串 与 反转串 的最长公共子序列
为什么？
因为回文串正读反读都一样。如果一个序列是回文，那它在原串中是这样，在反转串中也是这样——它就是两串的"公共子序列"！
比如"bbbab"反转后是"babbb"，它们的公共子序列"bbbb"长度为 4。
5.2 LCS 的状态转移
定义dp[i][j]：s[0..i-1]和t[0..j-1]的最长公共子序列长度。
if(s[i-1]==t[j-1])dp[i][j]=dp[i-1][j-1]+1;// 相等，一起选elsedp[i][j]=max(dp[i-1][j],dp[i][j-1]);// 不等，二选一5.3 完整代码
classSolution{publicintlongestPalindromeSubseq(Strings){Stringt=newStringBuilder(s).reverse().toString();intn=s.length();int[][]dp=newint[n+1][n+1];for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){if(s.charAt(i-1)==t.charAt(j-1)){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);}}}returndp[n][n];}}这个方法的妙处在于：你学一个 LCS，就白赚一道回文子序列！血赚不亏。
六、三种解法对比总结
| 解法 | 核心思想 | 时间 | 空间 | 面试推荐度 |
|---|---|---|---|---|
| 二维 DP | 区间动态规划 | O(n²) | O(n²) | ⭐⭐⭐⭐⭐ 必会 |
| 一维 DP | 滚动数组优化 | O(n²) | O(n) | ⭐⭐⭐⭐ 加分项 |
| LCS 转化 | 问题转化 | O(n²) | O(n²) | ⭐⭐⭐⭐ 展示知识广度 |
七、写在最后
动态规划就像谈恋爱——先解决小问题，再解决大问题。
单个字符是回文（长度为1）→ 两个字符能匹配吗 → 三个字符呢 → 最后搞定整个字符串。每一步都依赖前面已经算好的结果，就像每一段稳定的感情都建立在之前的经历之上。
至于空间优化？那就是学会断舍离——丢掉没用的东西，只保留真正需要的。
所以下次面试官问你这道题，你可以自信地说：
“这道题我有三种解法。第一种是标准的区间 DP；第二种优化到 O(n) 空间；第三种转化为 LCS。您想听哪一种？”
然后看着面试官满意的微笑，知道自己稳了。
参考资料
- LeetCode 516. Longest Palindromic Subsequence
- 《算法导论》第15章 动态规划
如果这篇文章对你有帮助，欢迎点赞收藏转发三连！你的支持是我写下去的最大动力！我们下期见，拜拜～ 👋
