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
