# 0516. 最长回文子序列
### 题目地址(516. 最长回文子序列)
### 题目描述
```
给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
示例 1:
输入:
"bbbab"
输出:
4
一个可能的最长回文子序列为 "bbbb"。
示例 2:
输入:
"cbbd"
输出:
2
一个可能的最长回文子序列为 "bb"。
提示：
1 <= s.length <= 1000
s 只包含小写英文字母
```
### 前置知识
* 动态规划
### 公司
* 阿里
* 腾讯
* 百度
* 字节
### 思路
这是一道最长回文的题目，要我们求出给定字符串的最大回文子序列。
解决这类问题的核心思想就是两个字“延伸”，具体来说
* 如果一个字符串是回文串，那么在它左右分别加上一个相同的字符，那么它一定还是一个回文串，因此`回文长度增加2`
* 如果一个字符串不是回文串，或者在回文串左右分别加不同的字符，得到的一定不是回文串,因此`回文长度不变，我们取[i][j-1]和[i+1][j]的较大值`
事实上，上面的分析已经建立了大问题和小问题之间的关联， 基于此，我们可以建立动态规划模型。
我们可以用 dp\[i]\[j] 表示 s 中从 i 到 j（包括 i 和 j）的回文序列长度， 状态转移方程只是将上面的描述转化为代码即可：
```js
if (s[i] === s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
}
```
base case 就是一个字符（轴对称点是本身）
### 关键点
* ”延伸“（extend）
### 代码
代码支持：JS，Python3
JS Code：
```js
/*
* @lc app=leetcode id=516 lang=javascript
*
* [516] Longest Palindromic Subsequence
*/
/**
* @param {string} s
* @return {number}
*/
var longestPalindromeSubseq = function (s) {
// bbbab 返回4
// tag : dp
const dp = [];
for (let i = s.length - 1; i >= 0; i--) {
dp[i] = Array(s.length).fill(0);
for (let j = i; j < s.length; j++) {
if (i - j === 0) dp[i][j] = 1;
else if (s[i] === s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
}
}
}
return dp[0][s.length - 1];
};
```
Python3 Code（记忆化递归）：
```py
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
@cache
def dp(l,r):
if l >= r: return int(l == r)
if s[l] == s[r]:
return 2 + dp(l+1,r-1)
return max(dp(l+1, r), dp(l, r-1))
return dp(0, len(s)-1)
```
Python3 Code(普通 dp)
```py
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n-1, -1, -1):
for j in range(i, n):
if i == j:
dp[i][j] = 1
elif 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]
```
**复杂度分析**
* 时间复杂度：枚举所有的状态需要 n^2 时间，状态转移需要常数的时间，因此总的时间复杂度为 $O(n^2)$
* 空间复杂度：我们使用二维 dp 存储所有状态，因此空间复杂度为 $O(n^2)$
### 相关题目
* [5.longest-palindromic-substring](/leetcode-solution/medium/5.longest-palindromic-substring.md)
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/516.longest-palindromic-subsequence.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.