C++で最長のパリンドロームサブシーケンス

文字列sがあるとすると、パリンドロームサブシーケンスの最長の長さをsで見つける必要があります。 sの最大長は1000であると想定できます。したがって、入力が「bbbab」のような場合、出力は4になります。考えられるパリンドロームのサブシーケンスの1つは「bbbb」です。

これを解決するには、次の手順に従います-

• x：=s、次にx、n：=sのサイズを逆にする
• nが0の場合、0を返します
• sの前に1つの空白スペースを追加してsを更新し、xの前に1つの空白スペースを追加してxを更新します
• ret：=0
• サイズ（n + 1）x（n + 1）の1つの行列dpを作成します
• 1からnの範囲のiの場合
  • nからnの範囲のjの場合
    • 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]
• return 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