C ++中最长的回文序列
假设我们有一个字符串s，我们必须找到最长回文子序列的长度s。我们可以假设s的最大长度为1000。因此，如果输入类似“bbbab”，则输出将为4。一种可能的回文子序列是“bbbb”。
为了解决这个问题，我们将遵循以下步骤-
x：=s，然后反转x，n：=s的大小
如果n为0，则返回0
通过在s之前添加一个空格来更新s，并通过在x之前添加一个空格来更新x
ret：=0
使一个矩阵dp的大小为（n+1）x（n+1）
对于我在1到n范围内
dp[i，j]：=dp[i，j–1]，dp[i–1，j]的最大值
如果x[i]=s[j]，则dp[i，j]：=dp[i，j]的最大值和1+dp[i–1，j–1]
对于j在n到n范围内
返回dp[n，n]
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestPalindromeSubseq(string s) {
string x = s;
reverse(x.begin(), x.end());
int n = s.size();
if(!n) return 0;
s = " " + s;
x = " " + x;
int ret = 0;
vector < vector <int> > dp(n + 1, vector <int>(n + 1));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n ; j++){
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
if(x[i] == s[j]) {
dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
}
}
}
return dp[n][n];
}
};
main(){
Solution ob;
cout << (ob.longestPalindromeSubseq("bbbab"));
}输入项
"bbbab"
输出结果
4