立志要熟練動態規劃，加油！
-
最長回文子串
給定一個字串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; } };
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/119226.html
標籤：其他
上一篇：順序存盤結構和鏈式存盤結構優缺點
下一篇：Hadoop程式運行一直卡到INFO mapreduce.Job: Running job: job_1578474456005_0034