随想录算法训练营第五十七天|647.回文子串、516.最长回文子序列

本文主要是介绍随想录算法训练营第五十七天|647.回文子串、516.最长回文子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

647.回文子串

public class Solution {public int CountSubstrings(string s) {char[] s1=s.ToCharArray();int ans=0;bool[,]dp=new bool[s1.Length,s1.Length];for(int i=s1.Length-1;i>=0;i--){for(int j=i;j<s1.Length;j++){if(s1[i]==s1[j]){if(j-i<=1){dp[i,j]=true;ans++;}else if(dp[i+1,j-1]==true){dp[i,j]=true;ans++;}}}}return ans;}
}

如果要知道Dp[i,j]是否回文子串，在得知Dp[i+1,j-1]是的情况下只需要判断两端S[i]是否等于S[j]，是的话Dp[i,j]则是回文子串。

516.最长回文子序列

public class Solution {public int LongestPalindromeSubseq(string s) {char[] s1=s.ToCharArray();int[,] dp=new int[s1.Length,s1.Length];for(int i=0;i<s1.Length;i++){dp[i,i]=1;}for(int i=s1.Length;i>=0;i--){for(int j=i+1;j<s1.Length;j++){if(s1[i]==s1[j]){dp[i,j]=dp[i+1,j-1]+2;}else{dp[i,j]=Math.Max(dp[i+1,j],Math.Max(dp[i,j],dp[i,j-1]));}}}return dp[0,s1.Length-1];}
}

需要判断三种情况，如果S[i]与S[j]相同，那么Dp[i][j] = Dp[i + 1,j - 1] + 2，加入S[j]的回文子序列长度为Dp[i + 1][j]，加入S[i]的回文子序列长度为Dp[i][j - 1]，那么Dp[i][j]一定是取最大的，即：Dp[i,j]=Math.Max(Dp[i+1,j],Math.Max(Dp[i,j],Dp[i,j-1]))。

这篇关于随想录算法训练营第五十七天|647.回文子串、516.最长回文子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---