目录

647. 回文子串

516.最长回文子序列

动态规划总结篇

---

647. 回文子串

dp数组的定义

dp[i][j]代表的是区间[i,j]的字串是否为回文字符，如果dp[i][j]为true,否则为false

递推公式

如果s[i]和s[j]相等的话

1.i==j

为同一个字符，dp[i][j] = True

2 i与j相差1

dp[i][j] = True

3.i与j相差大于1

看一下前面的区间是不是true

dp[i-1][j-1] == True

如果不相等，那么return false

初始化

dp[i][j]== False

遍历顺序

因为需要在相等的第三种情况，需要判断里面的区间是不是回文。但是如果从上往下，从左往右遍历的话，会直接使用dp[i+1][j-1]未初始化的情况。所以我们不能那么遍历，所以我们需要从下往上，从左往右遍历

 

class Solution:def countSubstrings(self, s: str) -> int:#dp数组的定义,dp[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]:#i==jif i == j:result += 1dp[i][j] = Trueelif j-i == 1:result += 1dp[i][j] = Trueelse:if dp[i+1][j-1]:result += 1dp[i][j] = Truereturn result

代码随想录

516.最长回文子序列

dp数组的定义

dp[i][j]指的是字符串在[i,j]范围内最长回文子序列的长度是dp[i][j]

递归公式

如果s[i]和s[j]相同:

就要把长度+2，因为加入新的两个数

dp[i][j] = dp[i-1][j-1]+2

如果不相同:

那么把s[i]放进去

dp[i][j]= dp[i][j-1]

把s[j]放进去

dp[i][j]=  dp[i-1][j]

初始化

如果i==j的话，一定是等于1的

遍历顺序

从下到上，从左到右

打印dp

最后返回就看i,j区间内，最长的长度

647. 回文子串，求的是回文子串，而本题要求的是回文子序列， 大家要搞清楚两者之间的区别。

代码随想录

class Solution:def longestPalindromeSubseq(self, s: str) -> int:#dp数组的定义dp = [[0]*len(s) for _ in range(len(s))]for i in range(len(s)):dp[i][i] = 1for i in range(len(s)-1,-1,-1):for j in range(i+1,len(s)):#如果s[i]==s[j]的话if s[i]==s[j]:dp[i][j] = dp[i+1][j-1]+2else:dp[i][j] = max(dp[i+1][j],dp[i][j-1])return dp[0][-1]

动态规划总结篇

代码随想录