P3126 [USACO15OPEN]回文的路径Palindromic Paths

农夫FJ的农场是一个N*N的正方形矩阵（2\le N\le 5002≤N≤500），每一块用一个字母作标记。比如说：

ABCD
BXZX
CDXB
WCBA

某一天，FJ从农场的左上角走到右下角，当然啦，每次他只能往右或者往下走一格。FJ把他走过的路径记录下来。现在，请你把他统计一下，所有路径中，回文串的数量（从前往后读和从后往前读一模一样的字符串称为回文串）。

第一行包括一个整数N，表示农场的大小，接下来输入一个N*N的字母矩阵。

输出一个整数，表示回文串的数量。

解析

看到这题题解不多，蒟蒻便想更加通俗易懂地分享一点自己的心得，欢迎大佬批评指正^_^

像这种棋盘形的两边同时做的dp还有
P1006 传纸条,
P1004 方格取数,
T35377 大教室中传纸条

一、思路改进

对于这种题目最暴力的方法无非是分别枚举左上角和右下角两点坐标

（f[ i ][ j ][ k ][ l ] = f[ i-1 ][ j ][ k+1 ][ l ] + f[ i-1 ][ j ][ k ][ l+1 ] + f[ i ][ j-1 ][ k+1 ][ l ] + f[ i ][ j-1 ][ k ][ l+1 ]）

一起往中间走，即当两个点重合时便有了路径——O（n^4），像这种数据较大的题会爆

于是便有了新的思路，由于两点是一起走的，步数相同，所以可以枚举步数，又因为横纵坐标之和等于所走路径长+1（横纵坐标会重合一点，可以看下图理解）,所以只需枚举两点的横坐标（j，k）就可以求出两点的纵坐标

| 1 | 2 | 3 | 4 | 5 |

1 左上角 E

2 D

3 C

4 B

5 A 右下角

i表示步数（注：左上角和右下角只有一种走法，我们可以从第二步开始走，又因为横纵坐标重合一点，为了使横坐标+纵坐标=i，我们可以从3开始枚举）

上图字母是路径长为5，i（所枚举的步数）为5+1=6的情况

设j为左边点的横坐标（纵坐标为i-j），k为右边点所走路径的竖直长【如上图点A，枚举到它时k为1，横坐标为n-(i-k)+1=n-i+k+1=5-6+1+1=1，纵坐标为n-k+1=5-1+1=5】

即f（i,j,k）=f（i-1,j,k）+f（i-1,j-1,k）+f（i-1,j,k-1）+f（i-1,j-1,k-1）【j-1，而i不变，说明点的纵坐标+1，其实这个式子与上面暴力的式子是一样的】

二、空间优化

然而，这题数据范围到了500，如果开500^3的数组会MLE，考虑到每次状态转移只需用到f(i-1,j,k)，可以用滚动数组优化空间

逆序枚举j、k【f[j][k]=f[j][k]+f[j-1][k-1]+f[j-1][k]+f[j][k-1]等式左侧步数为i，而右侧其实是上次枚举的状态，步数为i-1】（与01背包的滚动数组优化同理）即可避免覆盖还未转移的状态。

三、代码

只有两点字母相同时才能走，因此当两点字母不同时方案数为0，否则为每个可以走过来的状态的方案数之和

具体细节可以在代码中进一步理解

#include
#define rint register int
using namespace std;
char a[501][501];
int n;
long long f[501][501],ans;
int main() {
    cin>>n;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            cin>>a[i][j];
    if (a[1][1]!=a[n][n]) {
        cout<<0;
        return 0;
    }//如果左上角和右下角字母不同则无解
    f[1][1]=1;//当两点分别处于左上角和右下角时方案为1
    for (rint i=3; i<=n+1; i++)
        for (rint j=i-1; j>=1; j--)
            for (rint k=i-1; k>=1; k--) {
                if (a[j][i-j]==a[n-i+k+1][n-k+1])//（用j，k分别求出所对应的横纵坐标）此两点字母是否相同？
                    f[j][k]=(f[j][k]+f[j-1][k-1]+f[j-1][k]+f[j][k-1])%1000000007;
                else f[j][k]=0;//不相同则方案为0
            }
    for (int i=1; i<=n; i++)//统计所有方案数
        ans=(ans+f[i][i])%1000000007;//当j=k说明两点重合
    cout<<ans;
}