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