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"