> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/zi-fu-chuan/516-zui-chang-hui-wen-zi-xu-lie.md).

# \[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/)