C++ | Top-down Solution


#1
int getLongestPalindromicSubseq(vector<vector<int>>& memo, string& A, int i, int j) {
	if (j < 0 || i >= A.length())
		return 0;

	if (memo[i][j] != -1)
		return memo[i][j];

	if (A[i] == A[j])
		return memo[i][j] = getLongestPalindromicSubseq(memo, A, i + 1, j - 1) + 1;

	return memo[i][j] = max(getLongestPalindromicSubseq(memo, A, i + 1, j), getLongestPalindromicSubseq(memo, A, i, j - 1));
}

int Solution::solve(string A) {
    int lenA = A.length();
    vector<vector<int>> memo(lenA, vector<int>(lenA, -1));
    return getLongestPalindromicSubseq(memo, A, 0, lenA - 1);
}