---
# System prepended metadata
title: LC 516. Longest Palindromic Subsequence
tags: [medium, leedcode, DP, python, c++]
---
# LC 516. Longest Palindromic Subsequence
### [Problem link](https://leetcode.com/problems/longest-palindromic-subsequence/)
###### tags: `leedcode` `python` `c++` `medium` `DP`
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.
## Solution 1 - DP
#### Python
```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++
```cpp=
class Solution {
public:
int longestPalindromeSubseq(string s) {
vector> dp(s.size(), vector(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)類似
