C++ 中心最长的回文子序列

假设我们有一个字符串 s，需要找出 s 中最长的回文子序列的长度。我们可以假定 s 的最大长度为 1000。因此，如果输入类似于“bbbab”，那么输出将为 4。一个可能的回文子序列是“bbbb”。

为了解决这个问题，我们将遵循以下步骤：

  • x := s，然后反转 x，n := s 的大小
  • 如果 n 为 0，则返回 0
  • 更新 s，在 s 的前面添加一个空格，并更新 x，在 x 的前面添加一个空格
  • ret := 0
  • 制作一个大小为 (n + 1) x (n + 1) 的矩阵 dp
  • 对于范围从 1 到 n
    • 对于范围从 n 到 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] 中的最大值
  • 返回 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

更新日期：2020-05-02

690 次浏览

开启你的 职业生涯

完成课程并获得认证

开始
广告