647. 回文子串题目链接647. 回文子串 - 力扣LeetCode思路1. dp 数组定义dp[i][j]表示字符串下标 i 到 j 的子串是否是回文串True是False不是。2. 递推公式情况 1i j单个字符→ 一定是回文情况 2j i1两个相邻字符→s[i]s[j]就是回文情况 3j - i 1长度大于 2首尾字符相等且中间子串也是回文dp[i][j](s[i]s[j]) and dp[i1][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[i1][j-1] # 是回文就计数1 if dp[i][j]: res 1 return res516.最长回文子序列题目链接516. 最长回文子序列 - 力扣LeetCode思路1. dp 定义dp[i][j]字符串下标 ij的子串中最长回文子序列长度。2. 递推公式若s[i] s[j]首尾字符相同可以一起算进回文dp[i][j]dp[i1][j−1]2若s[i] ! s[j]舍弃左或舍弃右取最大值dp[i][j]max(dp[i1][j], dp[i][j−1])3. 初始化单个字符一定是回文dp[i][i]14. 遍历顺序逆序遍历 i从后往前j 从 i1 往后走。为什么要逆序遍历i:因为从递推公式里面看到i是用i1推出来的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[i1][j-1] 2 else: dp[i][j] max(dp[i1][j], dp[i][j-1]) return dp[0][n-1]