动态规划-最长回文子串
动态规划-最长回文子串
-
题目描述
给出一个字符串S,求S的最长回文子串的长度
样例:
字符串"PATZJUJZTACCBCC"的最长回文子串为"ATZJUJZTA",长度为9。
-
动态规划思想
令
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+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)
-
代码如下
#include <cstdio> #include <cstring> const int maxn = 1010; char s[maxn]; int dp[maxn][maxn]; int main(){ gets(S); int len = strlen(S),ans = 1; memset(dp,0,sizeof(dp)); // dp数组初始化为0 // 边界 for(int i = 0 ; i < len ; i++){ dp[i][i] = 1; if(i < len-1){ if(S[i] == S[i+1]){ dp[i][i+1] = 1; ans = 2; // 初始化时注意当前最长回文子串长度 } } } // 状态转移方程 for(int L = 3; L <= len ; L++){ // 枚举子串的长度 for(int i = 0 ; i + L - 1 < len ; i++){ // 枚举子串的起始端点 int j = i + L - 1; // 子串的右端点 if(S[i] == S[j] && dp[i+1][j-1] == 1){ dp[i][j] = 1; ans = L; // 更新最长回文子串长度 } } } printf("%d\n",ans); return 0; }