516

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n=s.length();
        int dp[n][n];
        memset(dp, 0, sizeof dp);

        // Case of 1 char.
        for(int i=0; i<n; i++)
            dp[i][i] = 1;

        // Case of 2+ chars.
        for(int len=2; len<=n; len++){
            for(int start=0; start<=n-len; start++){
                int end = start+len-1;
                if(s[start] == s[end])
                    dp[start][end] = 2+dp[start+1][end-1];
                else
                    dp[start][end] = max(dp[start+1][end], dp[start][end-1]);
            }
        }
        return dp[0][n-1];
    }
};