# \[516]\[中等]\[动态规划] 最长回文子序列

## 题目描述

[516. 最长回文子序列](https://leetcode-cn.com/problems/longest-palindromic-subsequence/)

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例 1:

```
输入:
"bbbab"
输出:
4
```

一个可能的最长回文子序列为 "bbbb"。

示例 2:

```
输入:
"cbbd"
输出:
2
```

一个可能的最长回文子序列为 "bb"。

提示：

* 1 <= s.length <= 1000
* s 只包含小写英文字母

## 解题思路

使用动态规划的方法.

**状态**

f\[i]\[j] 表示 s 的第 i 个字符到第 j 个字符组成的子串中，最长的回文序列长度是多少。

**转移方程**

如果 s 的第 i 个字符和第 j 个字符相同的话

f\[i]\[j] = f\[i + 1]\[j - 1] + 2

如果 s 的第 i 个字符和第 j 个字符不同的话

f\[i]\[j] = max(f\[i + 1]\[j], f\[i]\[j - 1])

**初始化**

f\[i]\[i] = 1 单个字符的最长回文序列是 1

**结果**

f\[0]\[n - 1]

**遍历顺序**

由于计算f\[i]\[j]时可能需要 f\[i+1]\[j-1] 即左下, f\[i+1]\[j] 即下方, f\[i]\[j - 1]即左方,

对角线的值在初始化时都确定时1, 因此在遍历时, i从最后向前遍历, j从i + 1遍历到n - 1, 这样可以保证每个子问题都已经算好了.

```python
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        if not n:
            return 0

        f = [[1] * n for _ in range(n)]

        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    f[i][j] = f[i + 1][j - 1] + 2 if j - i > 1 else 2
                else:
                    f[i][j] = max(f[i + 1][j], f[i][j - 1])
        return f[0][n - 1]
```

## 参考资料

* [动态规划，四要素](https://leetcode-cn.com/problems/longest-palindromic-subsequence/solution/dong-tai-gui-hua-si-yao-su-by-a380922457-3/)


---

# 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://kerasnoone.gitbook.io/garnet/suan-fa/zi-fu-chuan/516-zui-chang-hui-wen-zi-xu-lie.md?ask=<question>
```

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.