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:

`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]`

;`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:

`seq`

does not include`s[n-1]`

:`seq`

must be a palindromic subsequence of substring`s[0,n-2]`

;we must have first char of`seq`

includes`s[n-1]`

:`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];
}
```