区间dp
ref{:target=”_blank”}
枚举集合条件的时候,需要枚举坐标i和j是否包含在最长公共子串中
C++ 代码
class Solution {
public:
int longestPalindromeSubseq(string s) {
// f[i][j] 表示区间 [i,j] 内的回文子串长度
// 讨论4中情况,求max
// c1. 下标i和j在回文串中 f[i+1,j-1] + 2 && s[i] == s[j]
// c2. i在,j不在 f[i, j-1]
// c3. i不在,j在 f[i+1, j]
// c4. i和j都不在 f[i+1, j-1]
// 其中2和3有重叠,4是2的子集,4也是3的子集,所以 max(c1,c2,c3)就是答案
int n = s.size();
vector<vector<int>> f(n, vector<int>(n, 0));
// 边界初始化
for(int i=0; i<n; ++i)f[i][i] = 1;
// 枚举长度,记得是从 2->n
for(int len=2; len<=n; ++len) {
// 枚举起点
for(int i=0; i+len-1<n; ++i) {
int j= i+len-1;
if(s[i] == s[j]) f[i][j] = f[i+1][j-1] + 2;
f[i][j] = max(f[i][j], max(f[i+1][j], f[i][j-1]));
}
}
return f[0][n-1];
}
};