516.最长回文子序列

516.最长回文子序列

文章目录

• • • 题目
    • 思路
    • 代码
    • 运行结果
    • 总结

题目

'''
Description: 516.最长回文子序列
Autor: 365JHWZGo
Date: 2021-12-24 11:47:41
LastEditors: 365JHWZGo
LastEditTime: 2021-12-24 12:27:34
'''

思路

直观解题思路:

做了昨天那道647.回文子串后应该会发现，这道题和那道题有些相似，但又有一些本质上的区别，比如这道题是子序列，那道题其实相当于是子数组，即是连续的回文，中间无法删除某些多余字符。

那这该怎么解呢？
举例：s=“abcaba”
按照昨天的解题思路，得到的dp数组是

[[1, 0, 0, 0, 0, 0],
 [0, 1, 0, 0, 0, 0], 
 [0, 0, 1, 0, 0, 0],
 [0, 0, 0, 1, 0, 1], 
 [0, 0, 0, 0, 1, 0],
 [0, 0, 0, 0, 0, 1]]

得出的结果的最大值只有"aba",“a”,“b”,“c”,最大回文子串长度为3
但是，结果应该是5，“ababa” 或“abcba”

那么我们就应该反思，当两者末尾字符串相等时，不应该仅仅判断dp[i+1][j-1]了，而是应该判断所有它俩中间的字符串，只要有回文子串，结果就应该是正确的。

在此观点上，我从新赋予dp含义

思路：
1.确定dp数组以及下标含义
   dp[i][j]代表判断子串s[i:j+1]最长的回文子序列长度
2.确定递推公式
    头尾相等时
        情况一:头尾之间有子串
            dp[i][j] = dp[i+1][j-1]+2【中间最长子串+首尾两个字符】
        情况二:头尾之间无子串
            dp[i][j] = dp[i][j-1]+1 【中间最长子串0+尾字符】
    头尾不相等时
        dp[i][j] = max(dp[i+1][j],dp[i][j-1])
        dp[i+1][j]为s[i+1:j+1]
        dp[i][j-1]为s[i:j]
3.初始化dp数组
    对角线赋值为1
4.确定遍历顺序
    外循环从后往前
    内循环从前往后
5.举例推导
    s="abcaba"
    dp
    [[1, 1, 1, 3, 3, 5], 
     [0, 1, 1, 1, 3, 3], 
     [0, 0, 1, 1, 1, 3], 
     [0, 0, 0, 1, 1, 3], 
     [0, 0, 0, 0, 1, 1], 
     [0, 0, 0, 0, 0, 1]]

代码

class Solution(object):
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        dp = [[0 for _ in range(len(s))]for _ in range(len(s))]
        for i in range(len(s)-1,-1,-1):
            for j in range(i,len(s)):
                if i == j:
                    dp[i][j] = 1
                    continue
                if j-1 == i and s[i] == s[j]:
                    dp[i][j] = dp[i][j-1]+1
                    continue
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1]+2
                else:
                    dp[i][j] = max(dp[i+1][j],dp[i][j-1])

        # print(dp)
        return dp[0][-1]

运行结果

总结

这道题总体难度还ok，比较难想的可能是不相等时为什么要dp[i][j] = max(dp[i+1][j],dp[i][j-1])，其实你可以从简单的例子进行扩展，假设s=“ab”

那么dp为：

[[1,?]
 [0,1]]

很明显我们只需要知道 ？ 是多少就解决这道题了
先说？代表的位置是什么意思
dp[0][1]代表s[0:2]之间的最大回文子串长度

当s[0]!=s[1]时
那么我们就需要知道当以s[0]开头但不以s[1]结尾的回文字符串长度为多少：即 dp[i][j-1])
还有不以s[0]开头但以s[1]结尾的最长回文子串长度为多少：即dp[i+1][j]
两者取大

剩下的长的字符串都是通过小的子串得出的，每一步都选的最大，结果当然是最大～

还是挺考验人的思维能力的！再接再厉吧～