Problem Statement:

Given a string s, find the longest palindromic subsequence's length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

Constraints:

1 <= s.length <= 1000
s consists only of lowercase English letters.

Solution:

Approach

We denote dp[i][j] as the answer for the string s[i...j]. Hence final answer is dp[0][n-1] where n is length of string s.

Now, to get dp[i][j], we firstly start with the base case that is if i==j or i==j+1. Both of these are trivial to calculate. For other cases, we have three possiilities. Multiple of these can be true at a a time but the answer will still hold true.

The subsequence lies in s[i+1..j]
The subsequence lies in s[i..j-1]
s[i] and s[j] are part of the subsequence

We take a maximum of all these cases as the answer.

Code

 
int longestPalindromeSubseq(string s) 
{
    int n = s.length();
    vector<vector<int>> dp (n, vector<int>(n, -1));
    for (int len=1; len<=n; len++)
    {
        for (int i=0; i+len-1<n; i++)
        {
            int j = i+len-1;
            if (len==1) dp[i][j] = 1;
            else if (len==2) dp[i][j] = ((s[i]==s[j]) ? 2 : 1);
            else
            {
                int a = dp[i+1][j-1] + ((s[i]==s[j])?2:0);
                int b = dp[i+1][j];
                int c = dp[i][j-1];
                dp[i][j] = max(max(a,b),c);
            }
        }
    }
    return dp[0][n-1];
}

Analysis:

TC: $O(n^2)$ SC: $O(n^2)$