题意：给出一个n行m列的字符矩阵，从左上角走到右下角，每次只能往右或者往下走，求一共有多少种走法能得到回文串。
分析：
可以从两头开始考虑，每次只走一样字符的格子，这样得到的两个字符串拼起来之后就是一个回文串。
设d(step, x1, y2, x2, y2)表示从左上角(1, 1)z往右下走step个格子走到(x1, y1)，同时从右下角(n, m)往左上走step个格子走到(x2, y2)，而且两边得到一样字符串的方法数。
一开始判断一下左上角和右下角的字符是不是一样，若一样，d(1, 1, 1, n, m) = 1，若不一样则直接输出0.
状态转移：
如果s[x1][y2] = s[x2][y2]，而且x1 ≤ y1 && y1 ≤ y2
d(step, x1, y1, x2, y2) = d(step - 1, x1 - 1, y1, x2 + 1, y2) + d(step - 1, x1, y1 - 1, x2 + 1, y2) + d(step - 1, x1 - 1, y1, x2, y2 + 1) + d(step - 1, x1, y1- 1, x2, y2+ 1)
这是一个五维的状态空间太大了，空间优化：
首先如果已知step的话，x1和y1只要知道其中一个，就可以计算出另一个，x2和y2同理，所以我们可以把y1和y2去掉，这样把五维优化成三维。
另外一个优化就是，我们在递推的时候是按照step从小到大递推的，所以可以用滚动数组来优化，这样空间复杂度为O(n^2)。
另外要考虑一下奇偶的问题：
如果整个字符串长度为奇数的话，两个字符串会相遇在同一个格子
如果整个字符串长度为偶数的话，两个字符串会走到相邻的格子，要么是同一行左右相邻，要么是同一列上下相邻
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 typedef long long LL; 8 9 const int maxn = 500 + 10; 10 const int MOD = 1000000007; 11 12 int d[2][maxn][maxn]; 13 14 char G[maxn][maxn]; 15 16 void add(int& a, int b) { a += b; if(a >= MOD) a -= MOD; } 17 18 int main() 19 { 20 //freopen("in.txt", "r", stdin); 21 22 int n, m; 23 scanf("%d%d", &n, &m); 24 for(int i = 1; i <= n; i++) scanf("%s", G[i] + 1); 25 26 if(G[1][1] != G[n][m]) { puts("0"); return 0; } 27 28 d[1][1][n] = 1; 29 int cur = 1; 30 for(int s = 2; s <= (n + m) / 2; s++) 31 { 32 cur ^= 1; 33 memset(d[cur], 0, sizeof(d[cur])); 34 for(int x1 = 1; x1 <= s; x1++) 35 for(int x2 = n; x2 >= n - s + 1; x2--) 36 { 37 int y1 = s + 1 - x1; 38 int y2 = n + m + 1 - s - x2; 39 if(x1 > x2 || y1 > y2) continue; 40 if(G[x1][y1] == G[x2][y2]) 41 { 42 add(d[cur][x1][x2], d[cur^1][x1][x2]); 43 add(d[cur][x1][x2], d[cur^1][x1-1][x2]); 44 add(d[cur][x1][x2], d[cur^1][x1][x2+1]); 45 add(d[cur][x1][x2], d[cur^1][x1-1][x2+1]); 46 } 47 } 48 } 49 50 int ans = 0; 51 if((n + m) & 1) 52 { 53 for(int i = 1; i <= n; i++) add(ans, d[cur][i][i]), add(ans, d[cur][i][i+1]); 54 } 55 else 56 { 57 for(int i = 1; i <= n; i++) add(ans, d[cur][i][i]); 58 } 59 60 printf("%d ", ans); 61 62 return 0; 63 }