# 5-liner & 7-liner two versions O(N^2) clean DP (detailed explanation)

• It is natural to solve subsequence related problems with DP because a subsequence of a substring must be a subsequence of the string itself.

Solution 1:
We focus on the first `s[0]` and last char `s[n-1]` of string `s`. The longest palindromic subsequence `seq` of `s` must be one of the two cases:

1. `s[0] == s[n-1]`: `seq` must include `s[0], s[n-1]`, and therefore, `seq` without `s[0], s[n-1]` must be a longest palindromic subsequence of substring `s[1:n-2]`;
2. `s[0] != s[n-1]`: `seq` cannot include both `s[0]` and `s[n-1]`, so `seq` is either a palindromic subsequence of substring `s[1:n-1]` or `s[0:n-2]`.

Therefore, we have the straightforward DP recursion. Let `dp[i][j] =` length of longest palindromic subsequence of substring `s[i:j]` (`i<j`), then

• `dp[i][j] = s[i]==s[j]? dp[i+1][j-1]+2 : max(dp[i][j-1],dp[i+1][j])`.

Note: we must calculate `dp[i][j]` with smaller index difference `j-i` first before larger ones based on the recursion above.

``````    int longestPalindromeSubseq(string s) {
int n = s.size(); vector<vector<int>> dp(n, vector<int>(n));
for(int d = 0; d < n; d++) // d = j-i
for(int i = 0, j = i+d; j < n; i++,j++)
dp[i][j] = d? s[i]==s[j]? dp[i+1][j-1]+2 : max(dp[i][j-1],dp[i+1][j]) : 1;

return dp[0][n-1];
}
``````

Solution 2:
We focus only on the last char `s[n-1]` of string `s`. Any palindromic subsequence `seq` of `s` must be in one of the two categories:

1. `seq` does not include `s[n-1]`: `seq` must be a palindromic subsequence of substring `s[0,n-2]`;
2. `seq` includes `s[n-1]`: we must have first char of `seq` `s[k] = s[n-1]` because of palindrome.Therefore, `seq` without first char `s[k]` and last char `s[n-1]` must be a palindromic subsequence of substring `s[k+1,n-2]`.

Therefore, we have DP recursion:

• `dp[i][j] = max(dp[i][j-1], k<j? dp[k+1][j-1]+2 : 1)`,
where `k` = the index of first char `s[j]` in `s[i:]`.
``````    int longestPalindromeSubseq(string s) {
int n = s.size(); vector<unordered_map<char,int>> next(n); // next[i][c]: index of first c in s[i:]
for (int i = n-1; i >= 0; next[i][s[i]] = i--) if (i+1<n) next[i] = next[i+1]; // O(n^2)

vector<vector<int>> dp(n,vector<int>(n)); // dp[i][j]: result for substring s[i:j]
for (int d = 0; d < n; ++d)               // d = j-i: O(n)
for (int i = 0, j = i+d, k; j < n; ++i,++j) // O(n)
dp[i][j] = max(dp[i][j-1], (k=next[i][s[j]]) < j? dp[k+1][j-1]+2 : 1);

return dp[0][n-1];
}
``````

• Thanks! Very detailed explanation!

• @zzg_zzm Great solutions. However in your explanation you say:

If `s[0] == s[n-1]`, `seq` must include `s[0], s[n-1]`

, but this is not immediately obvious. Consider the string `bbacab` where `s[0] == s[n-1]`. You can make `seq` without using `s[0]`. So for completeness, you need to prove that:

When `s[0] == s[n-1]` then `LPS(s[1:n-2]) + 2 >= LPS(s[1:n-1])`.

• @jrusev Yes, you have a good point. When `s[0] == s[n-1]`, it is still not trivial to say longest palindrome in `s[1:n-2]` plus first and last chars will make the longest palindrome in entire `s`. The longest palindrome might use only one between first and last chars. But by the condition, I think this can be always adjusted to use both first and last chars which makes the same length of palindrome subsequence.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.