先说HDU 4632这道题，因为比较简单，题意就是给你一个字符串，然后给你一个区间，叫你输出区间内所有的回文子序列，注意是回文子序列，不是回文字串。
用dp[i][j]表示区间[i,j]内的回文子序列的个数。
那么可以得到状态转移方程：dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + a[i] == a[j] 。
#define N 1005
#define MOD 10007
int dp[N][N] ;
char a[N] ;
int main() {
int T ;
cin >> T ;
int cc = 0;
while( T -- ){
cin >> a ;
int l = strlen(a) ;
mem(dp ,0 ) ;
for (int i = 0 ; i < l ; i ++ )dp[i][i] = 1 ;
for (int i = 2 ; i <= l ; i ++ ){//枚举长度
for (int j = 0 ; j + i - 1 < l ; j ++ ){//枚举起点
int s = j ;
int e = j + i - 1 ;
if(a[s] == a[e])dp[s][e] ++ ;
else {
if(s + 1 <= e - 1){
dp[s][e] -= dp[s + 1][e - 1] ;
dp[s][e] = (dp[s][e] + MOD) % MOD ;
}
}
dp[s][e] += ( dp[s + 1][e] + dp[s][e - 1] ) % MOD ;
}
}
printf("Case %d: ",++cc) ;
cout << (dp[0][l - 1] + MOD ) % MOD << endl;
}
return 0 ;
}
CF 245H .这道题的题意差不多，不过他是给出区间，求出区间内的回文字串的个数。
上面那道题之所以我认为简单，是因为他不用判断[i , j ]之间是不是回文，因为他只需要计数就可以了。
而这道题，即使a[i] == a[j]，也要判断[i + 1 , j - 1]之内是不是回文。
这里我是多开一个数组来存当前区间是否是回文，用isP[i][j]来判断这个区间是否是回文。
初始化isP[i][i] = 1 ,dp[i][i] = 1 ，因为他本身肯定是回文。
当然初始化的时候还要注意isP[i + 1][i] = 1 ,因为我们注意到，当枚举到长度为2的时候，我们假设字符串为aa 。
那么首先a[i] == a[j] .然后还要判断[i + 1, j - 1]是否是回文，那么我们注意到，其实i + 1 > j - 1。实际上i + 1 = (j - 1 + 1)，但是这个情况其实也是回文。
所以我们要多初始化一位，让isP[i + 1][i] = 1 ,这是对长度为2的字串进行特殊的处理。
明白了这点。那么状态转移方程就很好写了：dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1] + a[i] == a[j] && isP[i + 1][j - 1]。
#define N 5005
char a[N] ;
int dp[N][N] ;
int isP[N][N] ;
int main() {
scanf("%s",a + 1) ;
int n ;
cin >> n ;
int l = strlen(a + 1) ;
for (int i = 1 ; i <= l ; i ++ )dp[i][i] = 1 ,isP[i][i] = 1 , isP[i + 1][i] = 1 ;
for (int i = 2 ; i <= l ; i ++ ) {
for (int j = 1 ; j + i - 1 <= l ; j ++ ) {
int s = j ;
int e = j + i - 1 ;
isP[s][e] = isP[s + 1][e - 1] && a[s] == a[e] ;
dp[s][e] += dp[s + 1][e] + dp[s][e - 1] - dp[s + 1][e - 1] + isP[s][e];
}
}
while(n -- ) {
int aa , bb ;
RD(aa) ;
RD(bb) ;
OT(dp[aa][bb]) ;
puts("") ;
}
return 0 ;
}