27.Longest Palindromic Subsequence

 class Solution {

public:

     int func(string &s,string &s1,int n,int m,vector<vector<int>>&dp)

     {

         if(n<0||m<0)return 0;

         if(s[n]==s1[m])

         {

              return dp[n][m]=1+func(s,s1,n-1,m-1,dp);

         }

         if(dp[n][m]!=-1)return dp[n][m];

         return dp[n][m]=max(func(s,s1,n,m-1,dp),func(s,s1,n-1,m,dp));

     }

    int longestPalindromeSubseq(string s)

     {

        string s1=s;

       reverse(s1.begin(),s1.end());

        vector<vector<int>>dp(s.size(),vector<int>(s.size(),-1));

        return func(s,s1,(int)s.size()-1,(int)s.size()-1,dp);

    }

};