本文主要是介绍【代码随想录】【回文子串】day57:● 647. 回文子串 ● 516.最长回文子序列 ● 动态规划总结篇，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
回文子串
def countSubstrings(self, s):# 动态规划解法# dp[i][j] s[i-j]区间的回文子串的数目 dp[i][j]取决于dp[i+1]和dp[j-1]count=0dp=[[False]*len(s) for _ in range(len(s))]for i in range(len(s)-1,-1,-1):for j in range(i,len(s)):if s[i]==s[j] :if j-i<=1:count+=1dp[i][j]=Trueelif dp[i+1][j-1]==True:count+=1dp[i][j]=Truereturn count
最长回文序列（不连续，可以删除某些元素形成回文）
def longestPalindromeSubseq(self, s):""":type s: str:rtype: int"""# dp[i][j]# 如果相等，最长的就是在基础上+1 如果不相等,就看[i+1:j]这一段和[i:j-1]这一段哪两个回文子串更长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)):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][len(s)-1]
这篇关于【代码随想录】【回文子串】day57:● 647. 回文子串 ● 516.最长回文子序列 ● 动态规划总结篇的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
