USACO - Palindromic Paths

Source: USACO 2015 US Open, Gold: Problem 2. Palindromic Paths
Tags: Dynamic Programming

Problem:
Cho ma trận N × N, mỗi ô của ma trận chứa một ký tự Alphabet in hoa. Tìm số lượng đường đi từ ô trái trên đến ô phải dưới sao cho xâu ký tự tạo thành từ đường đi là một xâu Palindrome, từ một ô chỉ có thể đi đến ô chung cạnh dưới hoặc bên phải ô đó. Kết quả có thể rất lớn nên cần in ra số dư khi chia cho 1e9 + 7.
1 ≤ N ≤ 500.

Ví dụ:
Input:
4
ABCD
BXZX
CDXB
WCBA

Output:
12

Explanation:
Có thể tạo ra các xâu sau:
1 xâu "ABCDCBA"
1 xâu "ABCWCBA"
6 xâu "ABXZXBA"
4 xâu "ABXDXBA"

Solution:
Ta có thể nhìn ra công thức DP đơn giản
DP[i1, j1, i2, j2] = DP[i1 - 1, j1, i2 + 1, j2] + DP[i1 - 1, j1, i2, j2 + 1]
                                      + DP[i1, j1 - 1, i2 + 1, j2] + DP[i1, j1 - 1, i2, j2 + 1]
trong đó DP[i1, j1, i2, j2] là số lượng cách để đường đi từ (1, 1) đến (i1, j1) giống với đường đi từ (N, N) đến (i2, j2) (tất nhiên là đường này đi ngược lại).
Tuy nhiên công thức này không hiệu quả với giới hạn N ≤ 500. Do đó ta sẽ thêm vài nhận xét để tối ưu công thức.
Để đường đi từ (1, 1) đến (i1, j1) giống với đường đi từ (N, N) về (i2, j2) thì đầu tiên là độ dài của 2 đường đi này phải giống nhau.
Nếu ta có độ dài và số hiệu dòng i1, i2 đang xét, ta có thể tìm ra được j1, j2 (len = 1..N).
i1 - 1 + j1 -  1 = len - 1 <=> j1 = len - i1 + 1
n - i2 + 1 + n - j2 + 1 = len - 1 <=> j2 = 2 * n - i2 - len + 3
Do đó ta có thể rút gọn công thức thành DP[len, i1, i2] = DP[len - 1, i1, i2] + DP[len - 1, i1, i2 + 1]
                                                                                                            + DP[len - 1, i1 - 1, i2] + DP[len - 1, i1 - 1, i2 + 1]
Về độ phức tạp thời gian thì đã okie, nhưng về độ phức tạp bộ nhớ thì sẽ bị quá giới hạn mem. Do đó ta sẽ thêm một nhận xét nữa là do tại mỗi DP[len] ta chỉ quan tâm đến DP[len - 1] nên ta sẽ chỉ lưu bằng 2 mảng.
Độ phức tạp: O(N ^ 3)

Code: (nộp bài ở USACO nhớ thêm nhập xuất file)
#include <iostream>

using namespace std;

const int MOD = 1e9 + 7;

int n, dp[2][500][500];
char c[500][500];

void inc(int& a, int b) {
    a = (a + b) % MOD;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> c[i][j];
    dp[0][0][n - 1] = c[0][0] == c[n - 1][n - 1];
    for (int len = 1; len < n; ++len)
        for (int i1 = 0; i1 <= len; ++i1)
            for (int i2 = n - 1 - len; i2 < n; ++i2) {
                int mask = len & 1, prevmask = mask ^ 1;
                dp[mask][i1][i2] = 0;
                int j1 = len - i1;
                int j2 = 2 * n - 2 - i2 - len;
                if (c[i1][j1] != c[i2][j2]) continue;
                if (j1 > 0 && j2 < n - 1) inc(dp[mask][i1][i2], dp[prevmask][i1][i2]);
                if (j1 > 0 && i2 < n - 1) inc(dp[mask][i1][i2], dp[prevmask][i1][i2 + 1]);
                if (i1 > 0 && j2 < n - 1) inc(dp[mask][i1][i2], dp[prevmask][i1 - 1][i2]);
                if (i1 > 0 && i2 < n - 1) inc(dp[mask][i1][i2], dp[prevmask][i1 - 1][i2 + 1]);
            }
    int res = 0;
    for (int i = 0; i < n; ++i)
        inc(res, dp[(n - 1) & 1][i][i]);
    cout << res;

}