学习目标

647. 回文子串
516.最长回文子序列
动态规划总结篇

学习内容

647. 回文子串

647. 回文子串 - 力扣（LeetCode）https://leetcode.cn/problems/palindromic-substrings/

class Solution:def countSubstrings(self, s: str) -> int:n = len(s)dp = [[0]*(n+1)for _ in range(n+1)]res = nfor i in range(n,0,-1):for j in range(n+1):if i>=j:dp[i][j]=1elif s[i-1]==s[j-1] and dp[i+1][j-1]:dp[i][j]=1res+=1#print(dp)return res

class Solution:def countSubstrings(self, s: str) -> int:n = len(s)res = 0for i in range(n):left = i-1right = i+1tmp = 1while left>-1 and right<n and s[left]==s[right]:tmp+=1left-=1right+=1res+=tmpfor i in range(n-1):j=i+1left = iright = jtmp = 0while left>-1 and right<n and s[left]==s[right]:tmp+=1left-=1right+=1res+=tmpreturn res

516.最长回文子序列

516. 最长回文子序列 - 力扣（LeetCode）https://leetcode.cn/problems/longest-palindromic-subsequence/

class Solution:def longestPalindromeSubseq(self, s: str) -> int:n = len(s)dp = [[0]*(n+1)for _ in range(n+1)]for i in range(n,0,-1):for j in range(n+1):if i>j:continueelif i==j:dp[i][j]=1elif s[i-1]==s[j-1]:dp[i][j]=dp[i+1][j-1]+2else:dp[i][j]=max(dp[i+1][j],dp[i][j-1])#print(dp)return dp[1][n]

class Solution:def longestPalindromeSubseq(self, s: str) -> int:n = len(s)dp = [0]*(n+1)for i in range(n,0,-1):tmp = [0]*(n+1)for j in range(n+1):if i>j:continueelif i==j:tmp[j]=1elif s[i-1]==s[j-1]:tmp[j]=dp[j-1]+2else:tmp[j]=max(dp[j],tmp[j-1])dp = tmp#print(dp)return dp[n]

problems/动态规划总结篇.md · programmercarl/leetcode-master（代码随想录出品） - Gitee.comhttps://gitee.com/programmercarl/leetcode-master/blob/master/problems/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%80%BB%E7%BB%93%E7%AF%87.md