516 最长回文子序列（区间dp）

我就是我 2022-08-30 04:05 175阅读 0赞

**1. 问题描述：**

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

**示例 1：**

输入：s = "bbbab"  
输出：4  
解释：一个可能的最长回文子序列为 "bbbb" 。

**示例 2：**

输入：s = "cbbd"  
输出：2  
解释：一个可能的最长回文子序列为 "bb" 。  
**提示：**  
1 <= s.length <= 1000  
s 仅由小写英文字母组成  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-palindromic-subsequence

**2. 思路分析：**

对于子序列的相关问题我们可以尝试**动态规划**的思路解决，动态规划主要有两个步骤：① 状态表示 ② 状态计算。由题可知我们需要求解出整个字符串的最长回文子序列，也即求解区间\[0, len(s)\]的最长回文子序列，所以我们可以考虑区间dp解决。可以定义二维的dp（区间dp一般定义为二二维），dp\[i\]\[j\]表示区间\[i, j\]的最长回文子序列的最大长度，如何进行状态的计算呢？状态计算主要考虑集合的划分，对于区间\[i, j\]我们可以考虑以下四种情况：① 区间i，j端点都包含在最长回文子序列中 ② 区间i端点包含，j端点不包含在最长回文子序列中 ③ 区间i端点不包含，j端点包含在最长回文子序列中 ④ 区间i，j端点都不包含在最长回文子序列中。对于①需要满足s\[i\] == s\[j\]，所以dp\[i\]\[j\] = dp\[i + 1\]\[j - 1\] + 2， 对于②，我们知道dp\[i\]\[j - 1\]既包含了区间端点i存在的情况又包含区间端点i不存在的情况，所以我们是可以直接使用dp\[i\]\[j - 1\]来计算区间②的情况，对于③也是类似的，dp\[i + 1\]\[j\]既包含了区间端点j在又包含了区间端点j不在的情况，所以也是可以用dp\[i + 1\]\[j\]来计算第③种情况（对于②③这两种情况对计算的结果是没有什么影响的），对于④可以发现是包含在②③这两种情况中的。所以我们在计算的时候只需要在①②③中取一个max即可。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

**3. 代码如下：**

class Solution:
        # 区间dp
        def longestPalindromeSubseq(self, s: str) -> int:
            n = len(s)
            dp = [[0] * n for i in range(n)]
            # 第一层枚举区间长度
            for l in range(1, n + 1):
                i = 0
                # i为区间起点, i + l - 1为区间终点
                while i + l - 1 < n:
                    j = i + l - 1
                    # 区间长度为1那么最长回文子序列的值为1
                    if l == 1:
                        dp[i][j] = 1
                    else:
                        # 区间的左右两个端点都是存在的
                        if s[i] == s[j]:
                            dp[i][j] += dp[i + 1][j - 1] + 2
                        # 计算其余的两种情况, 三种情况取一个max
                        else:
                            dp[i][j] = max(dp[i][j], dp[i + 1][j], dp[i][j - 1])
                    i += 1
            return dp[0][n - 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/482a2a1f91b7433e9e9cc31008cdc25f.png