# Leetcode 516 - Longest palindromic subsequence

** Note**:

- DP question
`dp[i][j]`

means the longest palindrome in`s[i, j]`

.- To compare
`s[i]`

and`s[j]`

, there are 2 situations:- When
`s[i] !== s[j]`

, we have to separately consider putting either`s[j]`

or`s[j]`

in`s[i+1, j-1]`

.

So, it’s`dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j])`

. - When
`s[i] === s[j]`

, there are also two situations:`i === j`

, it’s the same char! Then`dp[i][j] = 1`

.`i !== j`

, 2 different chars, then`dp[i][j] = dp[i+1][j-1] + 2`

.

- When

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" |

1 | /** |