10759번: 팰린드롬 경로 3

https://www.acmicpc.net/problem/10759

#include<stdio.h>
#define mod 1000000007
const int MAX_N = 500;
int n, dp[MAX_N][MAX_N];
char str[MAX_N][MAX_N + 1];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", str[i]);
        dp[i][i] = 1;
    }
    for (int i = n - 2; i >= 0; i--)
        for (int j = 0; j <= i; j++)
            for (int k = 0; k <= i; k++)
                dp[j][k] = (str[i - j][j] == str[n - 1 - k][n - 1 - i + k])
                *((dp[j][k] + dp[j + 1][k + 1]) % mod + (dp[j + 1][k] + dp[j][k + 1]) % mod) % mod;
    printf("%d", dp[0][0]);
    return 0;
}