算法提高——动态规划练习03

本文主要是介绍算法提高——动态规划练习03，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

最长回文子串

一、问题描述

　　给出一个字符串S，求S的最长回文子串的长度

　　例如：“PATZJUJZTACCBCC”的最长回文子串为"ATZJUJZTA"

二、解题思路

　　方法一：暴力解法，新建两个指针在字符串两端点，依次判断指针区间内的字符串是否为回文串，如果是则返回长度，否则就缩小区间再次判断。

　　方法二：动态规划，令dp[i][j]为区间i~j是否为回文串，如果是则为1，否则为0，如果S[i]==S[j]如果相等说明是回文子串，而且S[i+1]~S[j-1]也是回文子串，如果S[i+1]!=S[j-1]则说明不是回文子串，而且S[i]和S[j]也不是回文子串。通俗点说就是：长的串是回文串，则短的串就是回文串，如果短的串不是回文串，长的串一定不是回文串。

　　则当S[I]==S[j]时，dp[i][j]=dp[i+1][j-1]；当S[i]!=S[j]时，dp[i][j]=0;

三、代码

 1 #include <cstdio>
 2 #include <cstring>
 3 const int maxn = 1010;
 4 char S[maxn];
 5 int dp[maxn][maxn];
 6 int main(){
 7     gets(S);
 8     int len = strlen(S),ans = 1;//ans为最长回文子串长度 
 9     memset(dp,0,sizeof(dp));
10     for(int i=0;i<len;i++){
11         dp[i][i] = 1;
12         if(i<len-1){
13             if(S[i]==S[i+1]){
14                 dp[i][i+1] = 1;
15                 ans = 2;
16             }
17         }
18     }
19     for(int L=3;L<=len;L++){
20         for(int i=0;i+L-1<len;i++){
21             int j=i+L-1;
22             if(S[i] == S[j] && dp[i+1][j-1] == 1){//判断时，如果i和j的值相同而且i和j所夹的串是回文串，那么i~j就是回文串
23                 dp[i][j]=1;
24                 ans = L;
25             }
26         }
27     }
28     printf("%d\n",ans);
29     return 0;
30 } 

四、分析

　　首先对dp进行初始化，对于单个字符肯定是回文串所以dp[i][i]=1，对于长度为2的串，如果S[i]!=S[i+1]那么就不是回文串。

　　初始化后，就可以开始计算长度为3的串了，依次类推，计算长度为4的串。

这篇关于算法提高——动态规划练习03的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！