# 516. Longest Palindromic Subsequence

#### Medium

***

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.

```python
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        rev = s[::-1]
        dp = [[0]*(len(s)+1) for _ in range(len(s)+1)]
        length = len(s)
        for i in range(1, length+1):
            for j in range(1, length+1):
                if s[i-1] == rev[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[length][length]
```