Longest Palindromic Subsequence

Given a String, find the longest palindromic subsequence.

• Time : O(n^2)
• Space : O(n^2)

class Solution{
    int dp[505][505];
    int helper(string& S, int l, int r) {
        if(l > r) return 0;
        if(l == r) return 1;
        if(dp[l][r] != -1) return dp[l][r];
        int& res = dp[l][r] = max(helper(S, l + 1, r), helper(S, l, r - 1));
        if(S[l] == S[r])
            res = max(res, 2 + helper(S, l + 1, r - 1));
        return res;
    }
  public:
    int longestPalinSubseq(string A) {
        memset(dp, -1, sizeof dp);
        return helper(A, 0, A.length() - 1);
    }