1问题记述给出字符串s，求出s的最长回文部分列的长度。
根据2状态转移的想法，dp[i][j]表示从S[i]到S[j]表示的子串是否为回文子串，否则为1，否则为0。 这样，根据S[i]是否等于S[j]，可以将转移情况分为两类。
S[i]==S[j]时，只要S[i 1]至S[j-1]为回文子串，则S[i]至S[j]为回文子串； 恰恰相反。 如果S[i]！=S[j]，S[i]到S[j]一定不是回文子串。 这样就可以写状态转移方程了。
边界： dp[i][i]=1，dp[i][i 1]=(S[i]==S[i 1] )？ 1 : 0。
另外，还需要注意的是，如果按照I和j从小到大的顺序列举子串的两端，然后更新dp[i][j]，则不能保证计算出dp[i 1][j-1]，从而得不到正确的dp[i][j]。 解决方案是按照子串的长度和子串的初始位置进行枚举。 因为考虑到边界，它表示长度为1和2的子列，并且每次过渡都将子列的长度减少2。
33558 www.Sina.com/(可以达到o (n ^2)的时间复杂度) )。
# include cstdio # includecstringconstintmaxn=1010； char S[MAXN]； int dp[MAXN][MAXN]； int main () ) gets )； intlen=Strlen(s )、ans=1； 短信(DP，0，sizeof ) DP )； 初始化//DP序列for (inti=0； ilen； I ) ) /边界dp[i][i]=1； if(Ilen-1 ) if ) s[I]==s[I1] ) { dp[i][i 1]=1； ans=2； //初始化时注意当前最长回文子串的长度}}//状态转移方程for(intL=3； L=len； l () /枚举子串的长度for(intI=0； i L-1len； I )//枚举子串的开始端点int j=i L-1； //子串的右端点if(s[I]==s[j]DP[I1][j-1]==1) { dp[i][j]=1； ans=L； //更新最长回文子串长度}}printf('%dn '，ans )； 返回0； } 3除了动态规划方法外，还可以通过混列解决，降低时间复杂度
代码
hash+二分的思路
33558 www.Sina.com/# include iostream # include cstdio # include string # include vector # includealgorithmusingnamespacesttd tttd const LL MOD=1e9 7； //MOD为计算混列值时的模量const LL P=1e7 19； //P为计算混列值时的进制const LL MAXN=2e5 10； //字符串的最大长度//powP[i]为P^i%MOD，H1和H2分别为str和rstr的混列值LL powP[MAXN]、H1[MAXN]、H2[MAXN]； //init函数为powP函数void init () { powP[0]=1； for(intI=1； iMAXN； I ) {powp[I]=(powp[I-1]*p ) %MOD； }}//calH函数计算字符串str的混列值voidcalh(llh )、string str ) ) h(0)=str(0)。 //H[0]单独处理for (inti=1； istr.length (； I ) h(I )=) h(I-1 ) *pstr ) %MOD； }//calSingleSubH计算h[I.j]intcalsinglesubh[]，int i，intj]{if(I==0) return H[j]； 返回() h[j]-h[I-1]*powp[j-I1] ) %MOD MOD ) %MOD； (//设对称点为I，字符串长度为len，用[left，right]将回文半径一分为二)查找满足hashL==hashR的最后回文半径(/等效于查找满足条件的第一个hashL！=hashR的回文半径，减少1即可//isEven集中的鸭子回文为0，求爱回文为1intbinarysearch(intleft，int right，int len，int i， int isEven ) (while ) ) ) ) 65 //左半子串hash值H1[H1L.H1R]，右半子串值H2 [ h2l . h2r ] int h1l=I-midi seven，) INTH2L=Len-left-(Imid )、h2r=len-left-(IIS even )； intHashl=calsinglesubh(H1，H1L，H1R )； intHashr=calsinglesubh(H2，H2L，H2R )； if(Hashl！=Hashr(right=mid； //hash值各不相同，回文半径=mid else left=mid 1； //hash值相等，回文半径mid } return left-1； //返回最大回文半径(}int main ) ) { init )； 字符串str； 获取线(CIN，str )； calh(H1，str )； 恢复(str.begin )、str.end )； //反转字符串并选择calh(H2，str )； int ans=0； //奇回文for(intI=0； istr.length (； I () /二分钟上界在边界点I左右长度的小值上加上1intmaxlen=min(I，(int ) str.length )-1-i ) 1； intk=Binarysearch(0，maxLen，str.length )，I，0 )； ans=max(ans，k*2 1 )； //偶回文for(intI=0； istr.length (； I ) ) /二分钟上界在边界点I左右长度的小值上加1 (注意左边的长度为i 1) intmaxlen=min(I1，(int ) str.length ) )-1-i ) 1； intk=Binarysearch(0，maxLen，str.length )，I，1 )； ans=max(ans，k*2)； }printf('%dn '，ans )； 返回0； }