题目背景
还记得NOIP2011的寻宝吗？6年之后，小明带着他的妹子小芳，再次走上了寻宝的道路。
然而这次他们寻宝回来之后，小明被困在了一个迷宫中。
题目描述
迷宫是一个n*m的字符矩阵。
小明在这个矩阵的左上角，只能向下和向右走，去和在矩阵右下角的小芳会合。
小明必须将他走过的路径上的，经过的字符收集起来。如果到右下角时他收集到的这些字符连在一起是回文的，那么他就能够走出这个迷宫，否则他就会掉进陷阱出不来。
小明想知道有多少条路径能够让他走出这个迷宫。由于答案可能很大，请对1000000007取模。
输入输出格式
输入格式：
第一行两个整数n和m。
接下来n行，每行m个字符表示这个矩阵，全部均为小写字母
输出格式：
输出一行一个整数表示答案
输入输出样例
3 4aaabbaaaabba
3
说明
对于20%的数据，满足n∗m≤10
对于另外10%的数据，满足字符都是a
对于70%的数据，满足n,m≤60
对于100%的数据，满足n,m≤500
分析：一道比较考验基本功的dp题.
看到题面就应该能想到状态该怎么表示了，设f[i][j][k][l]表示小明走到了(i,j),小芳走到了(k,l)的方案数，那么该怎么转移呢？显然不能顺着推，因为不知道走过的字符串是啥，如果记录的话会有后效性，那么根据回文字符串的特点，小明从起点走，小芳从终点走，如果两个人所在地方的字符是一样的才能继续走，直到两个人碰面，答案累加，因为空间问题可以过70分.
后30%的数据只能开下500*500的数组，也就是说我们只能够保存两维.那么我们可以保存j和l,枚举当前走了多少步，因为方向一定，所以i和k能够推导出来。因为只保存了列的情况，如果直接推的话会计算重复，那么再开一个数组g,记录前一步的状态，f从g转移而来就可以了.
最后统计答案，如果n+m-1是奇数，那么最后汇合的地点一定是同一行，否则有可能是同一行，也有可能相差一行.
总结：这一类dp问题特征就是给你一个n*m的图，规定走的方向，让你求某些值.状态表示比较有规律，一般就是设f[i][j]表示走到了(i,j)的答案.如果题目变通一下让你走两次，那么可以开四维数组来表示状态.有时候也需要变通一下枚举的顺序，依题目而定，规定了走的方向，我们可以只用保存3维就可以推出第4维，可以优化时间，我们也可以保存2维，这样就需要一个辅助数组记录上一步的状态，既优化了时间，也优化了空间.
#include#include #include #include #include using namespace std;const int mod = 1000000007;int n, m,f[510][510],g[510][510];int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 };long long ans = 0;char s[510][510];int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1); if (s[1][1] == s[n][m]) f[1][m] = 1; else f[1][m] = 0; for (int t = 1; t < (n + m) / 2; t++) { for (int i = 1; i <= m; i++) for (int j = 1; j <= m; j++) { g[i][j] = f[i][j]; f[i][j] = 0; } for (int i = 1; i <= m; i++) for (int j = 1; j <= m; j++) if (g[i][j]) { int y11 = i, y2 = j, x1 = t - i + 1, x2 = n - t + m - j + 1; for (int k = 0; k < 2; k++) { for (int l = 2; l < 4; l++) { int nx1 = x1 + dx[k], ny1 = y11 + dy[k]; int nx2 = x2 + dx[l], ny2 = y2 + dy[l]; if (nx1 > n || ny1 > m || nx2 < 1 || ny2 < 1) continue; if (s[nx1][ny1] == s[nx2][ny2]) f[ny1][ny2] = (f[ny1][ny2] + g[i][j]) % mod; } } } } if ((n + m - 1) & 1) { for (int i = 1; i <= m; i++) ans = (ans + f[i][i]) % mod; } else { for (int i = 1; i <= m; i++) { ans = (ans + f[i][i]) % mod; ans = (ans + f[i][i + 1]) % mod; } } printf("%d\n", ans);return 0;}