# LC 516. Longest Palindromic Subsequence

### [Problem link](https://leetcode.com/problems/longest-palindromic-subsequence/)

###### tags: `leedcode` `python` `c++` `medium` `DP`

Given a string <code>s</code>, find the longest palindromic **subsequence** 's length in <code>s</code>.

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:**

- <code>1 <= s.length <= 1000</code>
- <code>s</code> consists only of lowercase English letters.

## Solution 1 - DP
#### Python

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        
        for i in range(n):
            dp[i][i] = 1

        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

        return dp[0][-1]

#### C++

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        for (int i = 0; i < s.size(); i++) {
            dp[i][i] = 1;
        }

        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i + 1; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
                }
            }
        }
        return dp[0].back();
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O($n^2$) | O($n^2$) |

## Note
sol1:
dp[i][j]: s[i] 到 s[j] 的最長回文字串 (包含s[i]與s[j])
跟[LC 647. Palindromic Substrings](https://hackmd.io/@Alone0506/B1FMTgk92)類似