遍历从i,j到x,y，i和j代表从中间出发到0 0，x,y是从中间出发到n,m，如果遍历的话是n^4，y可以用x算出来，所以遍历n^3就够了，但是数组开不下，用滚动数组。3维循环，
#include<bits\stdc++.h> using namespace std; typedef long long ll; #define pb push_back const int mod=1e9+7; int n,m; int dp[2][505][505]; char s[505][505]; void add(int &a,int b) { a+=b; if(a>=mod)a-=mod; } int main(){ scanf("%d%d%*c",&n,&m); for(int i=0;i<n;i++) scanf("%s",s[i]); memset(dp,0,sizeof(dp)); for(int i=n-1;i>=0;i--) for(int j=m-1;j>=0;j--) for(int x=i;x<n;x++) { int y=n+m-2-x-i-j; if(y<0)break; int ii=i&1; int &tmp=dp[ii][j][x]; if(s[i][j]!=s[x][y]) { tmp=0; continue; } if(i>x||j>y) { tmp=0; } else if(x+y-i-j<=1)tmp=1; else { tmp=0; if (i < n - 1) add(tmp, dp[!ii][j][x]); if (i < n - 1 && x) add(tmp, dp[!ii][j][x - 1]); if (j < m - 1) add(tmp, dp[ii][j + 1][x]); if (j < m - 1 && x) add(tmp, dp[ii][j + 1][x - 1]); } } printf("%d\n", dp[0][0][n - 1]); return 0; }
