## Question

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:4Explanation:One possible longest palindromic subsequence is "bbbb".

**Example 2:**

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

**Constraints:**

`1 <= s.length <= 1000`

`s`

consists only of lowercase English letters.

## Python Solution

class Solution: def longestPalindromeSubseq(self, s: str) -> int: l = len(s) matrix = [[0 for _ in range(l)] for _ in range(l)] for i in range(l): matrix[i][i] = 1 for i in range(l-1,-1,-1): for j in range(i+1,l): if s[i]==s[j]: matrix[i][j] = matrix[i+1][j-1] + 2 else: matrix[i][j] = max(matrix[i+1][j],matrix[i][j-1]) return matrix[0][-1]