class Solution {
public:
    int longestPalindromeSubseq(string s) {

        int i=0;
        int j=s.size()-1;
        int n=1001;
        vector<vector<int>>dp(n,vector<int>(n,-1));
        return  recursive_longestPalindromeSubseq(s,i,j,dp);
    }

    int recursive_longestPalindromeSubseq(string s,int i,int j,vector<vector<int>>&dp)
    {
        if(i>=j) return 0;


        int ans=0;
        if(dp[i][j]!=-1) return dp[i][j];

        if(s[i]==s[j])
        {
            ans=2+recursive_longestPalindromeSubseq( s,i+1,j-1,dp);
        }
        else
        {
            ans=max(recursive_longestPalindromeSubseq(s,i+1,j,dp),recursive_longestPalindromeSubseq( s,i,j-1,dp));
   }

        return dp[i][j]=ans;

    }


};