题目大意
原题链接，给定字符串求回文子序列数量。字符串长度 $len leq 1000 $。
算法思路
题干比较简单，而且数据量不大，很容易想到使用递推，关键在于如何定义递推中间值和递推式。博主做题的时候首先想到定义数组 (r[][]), $r[i][j], ileq j $ 表示以字符 (str[j]) 结尾，在区间 ([i,j]) 中的回文子序列数量，就可以得到递推式 $ r[i][j] = 1 + r[i][j-1] + sum_{k=i, str[k]=str[i]}^{j-1} {(1+r[k+1][j-1])} $. 递推的代码很好写，提交之后发现超时，仔细分析，复杂度为 (O(n^3))，无奈重新想递推关系。
吃过午饭，突然灵机一动，定义数组 (r[i][j]) 表示字符串区间 ([i,j]) 内的回文子序列数量，
[ egin{equation}
r[i][j] =
egin{cases}
0 & mbox{if $ i > j $ }\
1 & mbox{elif $ i = j $ }\
r[i][j-1] + r[i+1][j] + 1 & mbox{elif $ str[i] = str[j] $ }\
r[i][j-1] + r[i+1][j] - r[i+1][j-1] & mbox{if $ str[i]
eq str[j] $ }
end{cases}
end{equation}
]
大家注意 $r[i][j-1], r[i+1][j] $ 重复计算了区间 ([i+1,j-1])的回文子序列，应该减去，而(str[i]=str[j]) 情形时的1表示回文序列就是 (str[i],str[j]).这样复杂度就是 (O(n^2)) 啦，不会超时。
然而提交的时候出现了WA，百思不得其解，在我开始怀疑人生的时候突然想到，题目中要求对结果取模，因此可能在做减法的时候出现负数！
代码
#include <iostream>
#include <string>
#include <string.h>
using namespace std;
const int md = 100007;
string str;
int r[1004][1004]; // r[i][j] (i<=j) str([i,j]) str[j]
int dp(int a, int b)
{
if (r[a][b] != -1)
return r[a][b];
if (a > b)
r[a][b] = 0;
else if (a == b)
r[a][b] = 1;
else {
if (str[a] == str[b]) {
r[a][b] = dp(a, b - 1) + dp(a + 1, b) + 1;
}
else {
r[a][b] = dp(a, b - 1) + dp(a + 1, b) - dp(a+1, b-1);
}
}
r[a][b] = (r[a][b] + 2 * md) % md; // 防止负数!
return r[a][b];
}
int main()
{
int t;
cin >> t;
getline(cin, str);
for(int q=1;q<=t;q++) {
memset(r, 0xff, sizeof(int)*1004*1004);
getline(cin, str);
int len = str.length();
cout << "Case #" << q << ": " << dp(0, len - 1) << endl;
}
return 0;
}