647. 回文子串

• 思路
  • example
  • 连续子字符串
  • 区间DP

dp[i][j]: s[i,...,j] 是否为回文串
i-loop: 倒序

• 复杂度. 时间：, 空间:

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)  
        dp = [[False for _ in range(n)] for _ in range(n)]
        res = 0
        for i in range(n-1, -1, -1):
            for j in range(i, n):
                if s[i] == s[j]:
                    if j-i+1 <= 2:
                        dp[i][j] = True  
                    else:
                        dp[i][j] = dp[i+1][j-1] 
                else:
                    dp[i][j] = False  
                if dp[i][j]:
                    res += 1
        return res  

• 双指针， 空间
  • 中心扩散法
    • 中心：一个点
    • 中心：两个点

class Solution:
    def countSubstrings(self, s: str) -> int:
        def extend(s, center1, center2):
            res = 0
            left, right = center1, center2 
            while left >= 0 and right < n and s[left] == s[right]:
                res += 1
                left -= 1
                right += 1
            return res  
        n = len(s)  
        res = 0
        for i in range(n):
            res += extend(s, i, i)
            res += extend(s, i, i+1)
        return res  

516. 最长回文子序列

• 不连续子序列
• 单串，区间DP (二维）

dp[i][j]: s[i,...,j] 最长回文子序列长度

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

小结

• 回文连续子序列 (DP, 双指针)
• 回文不连续子序列 （DP)

DP 总结

动规五部曲分别为：
确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

• 基础题 （爬楼，不同路径）
• 背包问题 （零钱兑换，分割等和子集，单词拆分）
• 股票题 （状态）
• 打家劫舍 （状态）
• 子序列问题 (LIS, LCS, 编辑距离）
• 其他
  • 树形DP（打家劫舍系列里有一道）
  • 数位DP
  • 区间DP
  • 概率型DP
  • 博弈型DP

  • 状态压缩dp