区间型动态规划——最长回文子序列

电玩女神 2022-10-27 12:06 175阅读 0赞

#  #

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

示例 1:

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

输入:
    "bbbab"
    输出:
    4

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

### 1、题目分析 ###

这个题目可以划分为序列类型的动态规划，也可以划作为区间类型的动态规划。就我个人的思想而言，更接近区间类型的动态规划。

### 2、确定状态 ###

最优策略产生最长的回文子串T，长度是M

• 情况1：回文串长度是1，即一个字母

• 情况2：回文串长度大于1，那么必定有T\[0\]=T\[M-1\]

设T\[0\]是S\[i\], T\[M-1\]是S\[j\] ，T剩下的部分T\[1…M-2\]仍然是一个回文串，而且是S\[i+1…j-1\]的最长回文子串

因此我们可以假设状态f\[i\]\[j\]为S\[i……j\]的最长回文子串的长度。

### 3、转移方程 ###

假设状态f\[i\]\[j\]为S\[i……j\]的最长回文子串的长度

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]

### 4、初始条件和边界情况 ###

初始条件

– f\[0\]\[0\] = f\[1\]\[1\] = … = f\[N-1\]\[N-1\] = 1

• 一个字母也是一个长度为1的回文串

– 如果S\[i\] == S\[i+1\], f\[i\]\[i+1\] = 2

– 如果S\[i\] != S\[i+1\], f\[i\]\[i+1\] = 1

### 5、计算顺序 ###

这种类型的题目比较特殊，不能逐行去计算，需要按照j-i从小到大的顺序去计算

答案是f\[0\]\[N-1\]。

时间复杂度O(N\*N)，空间复杂度O(N\*N)

### 6、代码实现 ###

class Solution:
        def longestPalindromeSubseq(self, s: str) -> int:
            if len(s) == 0:
                return 0
            n = len(s)
            dp = [[0] * n for i in range(n)]
            for i in range(n):
                dp[i][i]=1
            for i in range(n-1,-1,-1):
                for j in range(i+1,n):
                    if s[i]==s[j]:
                        dp[i][j] = max(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][n - 1]

#  #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]: /images/20221024/7a9ef910d94f4fec9f53a031977b637f.png