【CF 570E】Pig and Palindromes

【CF 570E】Pig and Palindromes
3차원 dp는 대응하는 걸음수의 조합 수를 찾는다. 2, 3차원은 각각 1, 1과 n을 나타낸다. m 이 걸음수의 회문 종류는 상태수를 모두 저장하면 메모리가 너무 커서 스크롤 dp수 그룹을 만든다(최근에 배운 것)
코드는 다음과 같습니다.

#include <iostream>
#include <cstdio>
#include <cstring>
#define mod 1000000007
#define ll long long

using namespace std;

char str[501][502];
ll dp[2][501][501];

int main()
{
    int n,m,sp,i,e,j,k,y1,y2;
    ll ans;
    scanf("%d %d",&n,&m);
    for(i = 1; i <= n; ++i) scanf("%s",str[i]+1);

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

    dp[0][1][n] = 1;
    sp = n+m-2>>1;
    for(e = 1,i = 1; i <= sp; ++i, e ^= 1)
    {
        memset(dp[e],0,sizeof(dp[e]));
        for(j = 1; j <= min(i+1,n); ++j)
            for(k = n; k >= j && k >= max(n-i,1); --k)
            {
                y1 = i+2-j, y2 = m-i+n-k;
                if(str[j][y1] != str[k][y2]) continue;
                dp[e][j][k] = (dp[e^1][j-1][k] + dp[e^1][j][k+1] + dp[e^1][j-1][k+1]+dp[e^1][j][k])%mod;
            }
    }

    ans = 0;
    e ^= 1;
    if(n+m&1)
    {
        for(i = 1; i <= n; ++i) ans = (ans+dp[e][i][i]+dp[e][i][i+1])%mod;
    }
    else
    {
        for(i = 1; i <= n; ++i) ans = (ans+dp[e][i][i])%mod;
    }
    printf("%lld
",ans);
    return 0;
}