力扣5.最长回文子串（动态规划解题）

运用动态规划解题(C++)

我比较喜欢在代码中做解释，所以都在代码内部嵌入了解释，这个题的难点在于没有图解，这里我也是通过学习大佬的视频图解学会的，在这里给大家附上链接
https://leetcode.cn/problems/longest-palindromic-substring/solution/shi-pin-tu-jie-dong-tai-gui-hua-zui-chang-hui-wen-/
大家可以去听下，讲得特别好！
另外还有什么不懂得地方可以私信我哦！

string longestPalindrome(string s) {
int n=s.size();
if(n==1) return s;
int maxLen=1;
int begin=0;
vector<vector<int>> dp(n,vector<int>(n));
//长度为1时
for(int i=0;i<n;i++){
dp[i][i]=1;//长度为1时肯定是回文串
}
//接下来讨论长度大于1的时候
//L代表子字符串的长度
for(int L=2;L<=n;L++){
for(int i=0;i<n;i++){
//j代表右边界，i是左边界 
//L=j-i+1
int j=L+i-1;
if(j>=n) break; //越界
if(s[i]!=s[j]) dp[i][j]=0;//如果两端不相同，那么必定不是回文字符串
else{
if(j-i<3) dp[i][j]=1;
else dp[i][j]=dp[i+1][j-1];
}
//在判断此时的子串是否大于之前的回文串
if(dp[i][j]&&L>maxLen){
maxLen=L;
begin=i;
}
}
}
return s.substr(begin,maxLen);
}

最后

以上就是潇洒糖豆为你收集整理的力扣5.最长回文子串（动态规划解题）的全部内容，希望文章能够帮你解决力扣5.最长回文子串（动态规划解题）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。