day40-数据结构力扣
647. 回文子串
题目链接647. 回文子串 - 力扣（LeetCode）
思路
1. dp 数组定义
dp[i][j]：表示字符串下标 i 到 j 的子串是否是回文串，True是，False不是。
2. 递推公式
情况 1：
i == j（单个字符）→ 一定是回文情况 2：
j = i+1（两个相邻字符）→s[i]==s[j]就是回文情况 3：
j - i > 1（长度大于 2）首尾字符相等，且中间子串也是回文：dp[i][j]=(s[i]==s[j]) and dp[i+1][j−1]
3. 初始化
所有dp[i][i] = True，单个字符都是回文。
4. 遍历顺序
按子串长度从小到大遍历，先短后长。
5. 结果
遍历过程中统计所有dp[i][j] = True的总数。
提交
class Solution: def countSubstrings(self, s: str) -> int: n = len(s) # dp[i][j] 表示 s[i...j] 是否为回文子串 dp = [[False] * n for _ in range(n)] res = 0 # 遍历子串长度 len = 1 ~ n for length in range(1, n + 1): # 左端点i for i in range(n - length + 1): # 右端点j j = i + length - 1 if i == j: # 单个字符 dp[i][j] = True elif j == i + 1: # 两个字符 dp[i][j] = (s[i] == s[j]) else: # 多于两个字符：首尾相等且中间是回文 dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1] # 是回文就计数+1 if dp[i][j]: res += 1 return res516.最长回文子序列
题目链接516. 最长回文子序列 - 力扣（LeetCode）
思路
1. dp 定义
dp[i][j]：字符串下标 i～j的子串中，最长回文子序列长度。
2. 递推公式
若
s[i] == s[j]：首尾字符相同，可以一起算进回文dp[i][j]=dp[i+1][j−1]+2若
s[i] != s[j]：舍弃左或舍弃右，取最大值dp[i][j]=max(dp[i+1][j], dp[i][j−1])
3. 初始化
单个字符一定是回文：dp[i][i]=1
4. 遍历顺序
逆序遍历 i（从后往前），j 从 i+1 往后走。
为什么要逆序遍历i:
因为从递推公式里面看到，i是用i+1推出来的
5. 结果
dp[0][n-1]就是整个字符串最长回文子序列长度。
提交
class Solution: def longestPalindromeSubseq(self, s: str) -> int: n = len(s) # dp[i][j]：s[i...j] 最长回文子序列长度 dp = [[0] * n for _ in range(n)] # 初始化：单个字符 for i in range(n): dp[i][i] = 1 # i 逆序遍历 for i in range(n - 1, -1, -1): for j in range(i + 1, n): 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][n-1]