立志要熟练动态规划，加油！
-
最长回文子串
给定一个字符串s，找到s中最长的回文子串。你可以假设s的最大长度为 1000。
思路：设dp[l][r]表示s[l……r]是否回文，枚举右边界r，然后从0枚举l一直到r，dp[r][l] = s[r]==s[l] && （r-1-l-1+1<=1 || dp[l+1][r-1]），意思是当s[r]和s[l]相等时，则需要s[l+1~r-1]也回文，而如果l+1~r-1这一段长度小于等于1，那么肯定回文，否则看dp[l+1][r-1]是否为true即可，因为dp[l+1][r-1]是已经得到的。
c++：class Solution { public: string longestPalindrome(string s) { int len=s.length(),dp[1005][1005]; if(len<=1) return s; for(int i=0;i<len;i++) { for(int j=0;j<len;j++) dp[i][j]=0; } string ans=s.substr(0,1); int mx=1; for(int i=1;i<len;i++) { for(int j=0;j<i;j++) { if(s[i]==s[j]&&(i-j-2+1<=1||dp[j+1][i-1])) { dp[j][i]=1; if(i-j+1>mx) { ans=s.substr(j,i-j+1); mx=i-j+1; // cout<<ans<<endl; } } } } return ans; } };
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
