题目描述
给你一个字符串s，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab"输出：4解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd"输出：2解释：一个可能的最长回文子序列为 "bb" 。
提示：
1 <= s.length <= 1000s仅由小写英文字母组成
解决方案：
这段代码是基于记忆化递归求解字符串最长回文子序列（LPS）的实现，在原有递归框架上优化了字符串传参方式，并调整了状态转移的分支逻辑，核心思路是通过递归 + 缓存避免重复计算，从子串两端向中间收敛求解最长回文子序列长度。
核心逻辑
核心定义：
memo：二维记忆化数组（len×len），memo[begin][end]缓存子串s[begin..end]的最长回文子序列长度，初始值-1标记 “未计算”，避免重复递归；dfs(begin, end, s)：返回子串s[begin..end]的最长回文子序列长度，s传引用（string&）避免超长字符串拷贝。
递归边界：
begin > end（子串为空）：返回 0（空串无回文子序列）；begin == end（子串仅 1 个字符）：返回 1（单个字符自身是长度为 1 的回文子序列）。
记忆化优化：递归开始时先检查
memo[begin][end] != -1，若命中缓存则直接返回结果，将时间复杂度从纯递归的O(2n)降至O(n2)，大幅提升效率。核心状态转移：
- 若
s[begin] == s[end]（子串两端字符相等）：最长回文子序列长度 = 中间子串（begin+1到end-1）的结果 + 2（两端字符各贡献 1 位）； - 若
s[begin] != s[end]（子串两端字符不等）：最长回文子序列长度 = 删左字符（begin+1到end）或删右字符（begin到end-1）结果的最大值； - 最终再通过
max(ret, max(...))二次校验，确保覆盖所有可能的回文子序列场景（避免分支逻辑遗漏最优解）。
- 若
主函数逻辑：初始化记忆化数组，调用
dfs(0, len-1, s)计算整个字符串的最长回文子序列长度并返回。
关键特点
- 效率优化：字符串传引用减少拷贝开销，记忆化缓存避免重复递归，适配中短长度字符串；
- 逻辑冗余但安全：二次调用
max(dfs(begin+1,end,s), dfs(begin,end-1,s))虽有冗余（两端不等时已计算过），但能确保结果不遗漏最优解； - 边界清晰：覆盖空串、单字符等基础场景，结果无偏差。
总结
- 核心思路：通过记忆化递归从子串两端向中间收敛，利用 “两端相等 + 2、不等取删左 / 删右最大值” 的规则求解最长回文子序列；
- 关键设计：
memo数组是效率核心，传引用是性能优化核心，二次max校验是结果安全核心； - 局限性：超长字符串（如全
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); } };
)
