https://codeforces.com/problemset/problem/570/E

输入 n m (1≤n,m≤500) 和 n 行 m 列的字符矩阵，只包含小写字母。
你需要从左上角的 (1,1) 出发，到达右下角的 (n,m)。
每次只能向下或向右走。
问：有多少条路径对应的字符串是回文串？（见右图）
模 1e9+7。

input
3 4
aaab
baaa
abba

output
3

#include <bits/stdc++.h>

using namespace std;

const int N = 510, MOD = 1e9 + 7;
int dp[2][N][N];
// dp[N][N][N]:派两个人同时从左上角和右下角出发 且第一个人位于x1, 第二个人位于 x2
char g[N][N];
int n, m;

int main ()
{
    cin >> n >> m;
    int step = (n + m - 2) / 2;
    for(int i = 1; i <= n; i ++) scanf("%s", g[i] + 1);

    if(g[1][1] != g[n][m]){
        puts("0");
        return 0;
    }

    dp[0][1][n] = 1;
    for(int k = 1; k <= step; k ++)
    {
        memset(dp[k & 1], 0, sizeof dp[k & 1]); 
//注意清空滚动数组 由于当前状态只与上一层的状态有关，即使清空也会从上层状态转移过来，否则会导致多算
        for(int x1 = 1; x1 <= k + 1; x1 ++)
        {
            for(int x2 = n; x2 >= n - k; x2 --)
            {
                int y1 = k + 2 - x1, y2 = n - x2 + m - k;
                if(x1 > x2 || y1 > y2) continue;
                int &t = dp[k & 1][x1][x2];
                if(g[x1][y1] == g[x2][y2])
                {
                    t = (t + dp[k - 1 & 1][x1 - 1][x2]) % MOD;
                    t = (t + dp[k - 1 & 1][x1 - 1][x2 + 1]) % MOD;
                    t = (t + dp[k - 1 & 1][x1][x2]) % MOD;
                    t = (t + dp[k - 1 & 1][x1][x2 + 1]) % MOD;
                }
            }
        }
    }
    int res = 0;
    for(int i = 1; i <= n; i ++) res = (res + dp[step & 1][i][i]) % MOD;
    if(n + m & 1){
        for(int i = 1; i <= n; i ++) res = (res + dp[step & 1][i][i + 1]) % MOD;
    }
    cout << res << endl;
    return 0;
}