Both recursive memoisation and iteration implemented


#1
int lps(string A,int i,int j,vector<vector<int>> &dp){
    if(i>j) return 0;
    if(dp[i][j]!=-1) return dp[i][j];
    if(i==j) return dp[i][j]=1;
    if(A[i]==A[j]) dp[i][j]=2+lps(A,i+1,j-1,dp);
    else dp[i][j]=max(lps(A,i+1,j,dp),lps(A,i,j-1,dp));
    return dp[i][j];
}
int Solution::solve(string A) {
    /*string B=A;
    reverse(B.begin(),B.end());*/
    vector<vector<int>> dp(A.size(),vector<int> (A.size(),-1));
    /*for(int i=1;i<=A.size();i++){
        for(int j=1;j<=A.size();j++){
            if(A[i-1]==B[j-1]) dp[i][j]=1+dp[i-1][j-1];
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    return dp[A.size()][A.size()];*/
    return lps(A,0,A.size()-1,dp);
}