day165—递归—最长回文子序列（LeetCode-516）

题目描述

给你一个字符串s，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"输出：4解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"输出：2解释：一个可能的最长回文子序列为 "bb" 。

提示：

• 1 <= s.length <= 1000
• s仅由小写英文字母组成

解决方案：

这段代码是基于记忆化递归求解字符串最长回文子序列（LPS）的实现，在原有递归框架上优化了字符串传参方式，并调整了状态转移的分支逻辑，核心思路是通过递归 + 缓存避免重复计算，从子串两端向中间收敛求解最长回文子序列长度。

核心逻辑

1. 核心定义：

   • memo：二维记忆化数组（len×len），memo[begin][end]缓存子串s[begin..end]的最长回文子序列长度，初始值-1标记 “未计算”，避免重复递归；
   • dfs(begin, end, s)：返回子串s[begin..end]的最长回文子序列长度，s传引用（string&）避免超长字符串拷贝。

2. 递归边界：

   • begin > end（子串为空）：返回 0（空串无回文子序列）；
   • begin == end（子串仅 1 个字符）：返回 1（单个字符自身是长度为 1 的回文子序列）。

3. 记忆化优化：递归开始时先检查memo[begin][end] != -1，若命中缓存则直接返回结果，将时间复杂度从纯递归的O(2n)降至O(n2)，大幅提升效率。

4. 核心状态转移：

   • 若s[begin] == s[end]（子串两端字符相等）：最长回文子序列长度 = 中间子串（begin+1到end-1）的结果 + 2（两端字符各贡献 1 位）；
   • 若s[begin] != s[end]（子串两端字符不等）：最长回文子序列长度 = 删左字符（begin+1到end）或删右字符（begin到end-1）结果的最大值；
   • 最终再通过max(ret, max(...))二次校验，确保覆盖所有可能的回文子序列场景（避免分支逻辑遗漏最优解）。

5. 主函数逻辑：初始化记忆化数组，调用dfs(0, len-1, s)计算整个字符串的最长回文子序列长度并返回。

关键特点

• 效率优化：字符串传引用减少拷贝开销，记忆化缓存避免重复递归，适配中短长度字符串；
• 逻辑冗余但安全：二次调用max(dfs(begin+1,end,s), dfs(begin,end-1,s))虽有冗余（两端不等时已计算过），但能确保结果不遗漏最优解；
• 边界清晰：覆盖空串、单字符等基础场景，结果无偏差。

总结

1. 核心思路：通过记忆化递归从子串两端向中间收敛，利用 “两端相等 + 2、不等取删左 / 删右最大值” 的规则求解最长回文子序列；
2. 关键设计：memo数组是效率核心，传引用是性能优化核心，二次max校验是结果安全核心；
3. 局限性：超长字符串（如全a的千级长度）仍会因递归栈溢出失效，需结合全相同字符特殊优化或迭代 DP。

函数源码：

class Solution { public: vector<vector<int>> memo{}; int dfs(int begin,int end,string& s){ if(begin>end) return 0; if(begin==end) return 1; int ret=0; if(memo[begin][end]!=-1){ return memo[begin][end]; } if(s[begin]==s[end]){ ret = dfs(begin+1,end-1,s)+2; } else{ ret = max(dfs(begin+1, end, s), dfs(begin, end-1, s)); } ret = max(ret,max(dfs(begin+1,end,s),dfs(begin,end-1,s))); memo[begin][end]=ret; return ret; } int longestPalindromeSubseq(string s) { int len=s.length(); memo.assign(len,vector<int>(len,-1)); return dfs(0,len-1,s); } };