C++ Solution using DP


#1
typedef long long int ll;
#define forin(i, x, n) for(int i=x;i<n;i++)
#define forrev(i, x, n) for(int i=n-1;i>=x;i--)
#define  T     int ttt; cin >> ttt; while(ttt--)
#define vint vector<int>
#define vpair vector<pair<int,int>>
int lcshelper(string &A,int n,int m,vector<vint> &dp){
    if(n>m){
        return 0;
    }
    if(n==m){
        // cout << "Check2\n";
        return 1;
    }
    if(dp[n][m]!=-1){
        return dp[n][m];
    }
    if(A[n]==A[m]){
        // cout << "Check1\n";
        dp[n][m]=2+lcshelper(A,n+1,m-1,dp);
        return dp[n][m];
    }
    else{
        // cout << "Check3\n";
        dp[n][m]=max(lcshelper(A,n,m-1,dp),lcshelper(A,n+1,m,dp));
        return dp[n][m];
    }
}
int Solution::solve(string A) {
    int n=A.length();
    vector<vint> dp;
    vint res(n+1,-1);
    forin(i,0,n+1){
        dp.push_back(res);
    }
    return lcshelper(A,0,n-1,dp);
}