动态规划之最长回文子序列

╰+攻爆jí腚メ 2023-09-30 21:22 87阅读 0赞

[516. 最长回文子序列][516.]

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
    
    子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
    
     
    示例 1：
    
    输入：s = "bbbab"
    输出：4
    解释：一个可能的最长回文子序列为 "bbbb" 。
    示例 2：
    
    输入：s = "cbbd"
    输出：2
    解释：一个可能的最长回文子序列为 "bb" 。
     
    
    提示：
    
    1 <= s.length <= 1000
    s 仅由小写英文字母组成

题解：

用 `dp[i][j` 表示字符串 s 下标范围 `[i, j]` 内最长回文子序列的长度，假设字符串 s 的长度为 n，则只有当 `0<=i<j<n` 时，才会有 `dp[i][j] > 0`，否则有 `dp[i][j]=0`

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):
                # bad case，若只有一个字符，最长回文子序列长度是 1，dp[i][j] = 1 (i == j)
                dp[i][i] = 1	
                for j in range(i+1, n):
                    # 它俩一定在最长回文子序列中
                    if s[i] == s[j]:
                        dp[i][j] = dp[i+1][j-1] + 2
                    else:
                        # s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长
                        dp[i][j] = max(dp[i+1][j], dp[i][j-1])
            
            return dp[0][n-1]

> 参考：[子序列问题通用思路|最长回文子序列][Link 1]

[516.]: https://leetcode.cn/problems/longest-palindromic-subsequence/
[Link 1]: https://leetcode.cn/problems/longest-palindromic-subsequence/solution/zi-xu-lie-wen-ti-tong-yong-si-lu-zui-chang-hui-wen/