dp基础题目1 ： 最长回文子串

最长回文子串

题目：

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

样例

字符串"PATZJUJZTACCBCC"的最长回文子串为"ATZJUJZTA",长度为9。

思路

dp[i][j] 表示第i个到第j个 是否可以构成回文序列 true表示可以 false表示不行 首先 设置边境条件 即dp[i][i] = true 并且求出序列数为2的回文序列 并标记 找出状态转移方程： dp[i][j] = (a[i]==a[i+1] && dp[i+1][len+i-1]?true:flase); 枚举回文序列长度，并更新答案ans

代码

#include<iostream> #include<algorithm> #include<cstring> using namespace std; char a[100]; bool dp[100][100]; //dp[i][j]表示从i到j的所有序列可否构成回文序列 int main(){ int ans = 0; cin >>a; int len = strlen(a); for(int i = 0;i<len;i++){ dp[i][i] = true; if(i<len-1){ if(a[i] == a[i+1]){ dp[i][i+1] = true; ans = 2; } } } for(int L = 3;L<=len;L++){ for(int i = 0;i+L-1<len;i++){ int lens = L+i-1; if(a[i] == a[lens] && dp[i+1][lens-1]){ dp[i][lens] = true; ans = L; } } } cout <<ans<<endl; return 0; }