思路来源 灵茶山艾府
题目要求找到最长 回文 子序列
选或者不选 从两侧向内缩小问题规模、
if(s[i]==s[j])
return dfs(i+1,j-1)+2//从0--s.size()的最长公共子序列的长度为，1--s.size()-1的最长公共子序列的长度+2
else
if(s[i]!=s[j])
return max(dfs(i+1,j),dfs(i,j-1));
不相同，左右两边的字符分别消掉对方再比较最大值
边界条件
if i>j
return 0
if(i==j)
return 1;
利用记忆化搜索
代码如下
class Solution {
vector<vector<int>>used;
int dfs(string &s,int i,int j)
{
if (i == j)
return 1;
if (i > j)
return 0;
if(used[i][j]!=-1)
return used[i][j];
if (s[i] != s[j])
{
used[i][j]=max(dfs(s, i + 1, j), dfs(s, i, j - 1));
}
else
{
used[i][j]=dfs(s, i + 1, j -1)+2;
}
return used[i][j];
}
public:
int longestPalindromeSubseq(string s) {
used=vector<vector<int>>(s.size()+1,vector<int>(s.size()+1,-1));
return dfs(s,0,s.size()-1);
}
};然后是改成递推
这里用的是二维数组，每个数组的含义是
从下标i到j的范围，最长的回文子序列
ai解释：
- i 是子串的起点，j 是子串的终点。
- dp[i][j] 的值依赖于更小的子问题，如 dp[i+1][j] 或 dp[i][j-1]。
- dp[i][j] 的值依赖于更小的子问题，如 dp[i+1][j] 或 dp[i][j-1]。
例子 假设 s = "abdbca"，我们看 dp[1][4]，也就是子串 "bdb"：
- s[1] = 'b'，s[4] = 'b'，满足 s[i] == s[j]。
- 去掉 s[1] 和 s[4] 后，s[2:3] = "d"，这个子串的最长回文子序列是 1。
- 所以 dp[1][4] = dp[2][3] + 2 = 1 + 2 = 3（即 "bdb"）。
代码如下：
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector<int>>dp(n+ 1, vector<int>(n + 1, 0));
for (int i = 0;i < n;i++)
{
dp[i][i] = 1;
}
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[i + 1][j - 1] + 2;
}
else
{
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n-1];
}
};