Longest Palindromic Subsequence

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

c++

int helper(string& s, vector<vector<int>>& dp, 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,dp,l+1,r), helper(s,dp,l,r-1));
    if(s[l] == s[r]) res = max(res, helper(s,dp,l+1,r-1) + 2);
    return res;
}
int Solution::solve(string A) {
    int n = A.size();
    vector<vector<int>> dp(n, vector<int>(n, -1));
    return helper(A,dp,0,n-1);
}