[BOJ] 백준 10759 팰린드롬 경로 3

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

Approach

DP[][] = 문자열이 팰린드롬인 경우의 수

 

▶ 동적계획법(Dynamic Programming, DP) 

동적계획법(Dynamic Programming, DP)

---

#include <stdio.h>
#define LL long long
const int MAX_N = 500 + 2;
const int MOD = 1000000007;
inline LL add(LL A, LL B) { return (A % MOD) + (B % MOD); }
int N, DP[MAX_N][MAX_N];
char str[MAX_N][MAX_N + 1];

void init()
{
    for (int i = 0; i <= N; ++i)
    {
        for (int j = 0; j <= N; ++j)
        {
            DP[i][j] = 0;
            str[i][j] = '\0';
        }
    }
}

void input()
{
    scanf("%d", &N);
    init();
    for (int i = 0; i < N; i++) {
        scanf("%s", str[i]);
        DP[i][i] = 1;
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    input();
    for (int i = N - 2; i >= 0; i--)
    {
        for (int j = 0; j <= i; j++)
        {
            for (int k = 0; k <= i; k++)
            {
                if (str[i - j][j] != str[N - 1 - k][N - 1 - i + k])
                    DP[j][k] = 0;
                else
                    DP[j][k] = add(DP[j][k] + DP[j + 1][k + 1], DP[j + 1][k] + DP[j][k + 1]) % MOD;
            }
        }
    }
    printf("%d\n", DP[0][0]);
    
    return 0;
}