第九章动态规划Part13

haohaoscnblogs / 2024-09-01 / 原文

任务
- 647. 回文子串
  - 思路
- 516. 最长回文子序列
  - 思路

任务

647. 回文子串

给你一个字符串 s ，请你统计并返回这个字符串中回文子串的数目。

回文字符串是正着读和倒过来读一样的字符串。

子字符串是字符串中的由连续字符组成的一个序列。

思路

这道题的DP思路不是很直观，dp表示的不是某区间的回文子串数目，dp[i][j]表示[i,j]是否是回文子串，如果是则加结果加一，遍历完整个区间后，得到整个区间每个子区间各种情况的回文子串，累加起来即是所求。
那么只有s[i] == s[j]时，区间长度为1 和为2时，直接赋True，区间长度大于2时，如果 dp[i+1][j-1] 为True，则dp[i][j]为True
注意初始化和遍历顺序

class Solution:
    def countSubstrings(self, s: str) -> int:
        #dp[i][j]表示[i,j]是否是回文子串
        dp = [[False] * len(s) for _ in range(len(s))]
        result = 0
        for i in range(len(s)-1,-1,-1):
            for j in range(i,len(s)):
                if s[i] == s[j]:
                    if j-i <= 1: 
                        dp[i][j] = True
                        result += 1
                    elif dp[i+1][j-1]:
                        dp[i][j] = True
                        result += 1
        return result

516. 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

思路

该题比上题直观很多，dp[i][j]表示[i,j]范围内的最长回文子序列长度。s[i] == s[j]时，长度拓展2；不相等时，长度取dp[i+1][j]和dp[i][j-1]的最大值（因为不等时说明两边不能同时加入，就取一边加入后的最大值）。

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        #dp[i][j]表示[i,j]范围内的最长回文子序列长度
        dp = [[0] * len(s) for _ in range(len(s))]
        for i in range(len(s)): # i==j时表示单元素区间，此时为最长回文子序列长度为1
            dp[i][i] = 1
        for i in range(len(s)-1,-1,-1):
            for j in range(i+1,len(s)):
                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])
        return dp[0][len(s)-1]