leetcode 动态规划（基础版）最长回文字串

本文主要是介绍leetcode 动态规划（基础版）最长回文字串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

题解：

首先回文子串肯定是连续的，如果用dp来做就需要找出一个串的所有连续子串，枚举一个串所有连续子串的可行方案是首先枚举子串的右端点，范围是（0~s.size()-1）,在每一个右端点中枚举左端点，范围是（0~右端点）。在能够枚举出每一个子串后再在此基础上做状态转移即可。当前连续子串是回文串条件是左右端点字符相同，并且左右端点往中间移动一个位置后形成的合法子串也是回文串。在枚举中找到最大回文子串即可。

string longestPalindrome(string s) {string ans;int dp[1005][1005]={0};for(int i=0;i<s.size();i++){for(int j=0;j<=i;j++){dp[j][i]=s[i]==s[j];if(j+1<=i-1)dp[j][i]&=dp[j+1][i-1];if(dp[j][i]){if(i-j+1>ans.size())ans=s.substr(j,i-j+1);}}}return ans;}

题后反思：

最重要的两点：

1.如何枚举出每个连续子串，并表示出它们的状态

2.当前连续子串是回文串的条件

本题其实更像递归似的状态转移

这篇关于leetcode 动态规划（基础版）最长回文字串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---