HDU 2067 小兔的棋盤：卡特蘭數應用

問題描述

從 (0,0) 走到 (n,n) 的最短路徑（僅向上/向右）共 C(2n, n) 條。若限制路徑不穿越對角線 y=x（可接觸），求合法路徑數。輸入多組 n (1≤n≤35)，-1 結束。輸出格式：序號 n 答案。

數學模型：卡特蘭數

不穿越對角線的最短路徑數 = 第 n 項卡特蘭數 Cₙ = (1/(n+1)) * C(2n, n)。

本題輸出為 2 * Cₙ（樣例：n=1 → 2，n=3 → 10，n=12 → 416024），因題目可能將「不穿越」理解為嚴格不超過對角線，雙倍計算對稱情況，或輸出格式要求。代碼中直接輸出 f[n][n]*2 或 h[n]*2。

兩種計算方法

方法一：遞歸定義（動態規劃）

h[0] = 1; h[n] = Σ h[i] * h[n-1-i] (i=0..n-1)

long long h[45];
void catalan() {
    h[0] = 1;
    for (int i = 1; i < 36; ++i) {
        h[i] = 0;
        for (int j = 0; j <= i; ++j)
            h[i] += h[j] * h[i - j - 1];
    }
}

方法二：網格 DP（直觀幾何）

f[i][j] 表示從 (0,0) 走到 (i,j) 且不超過對角線的路徑數（i ≤ j）。
遞推：f[i][j] = f[i-1][j] + f[i][j-1]（來自左/下），邊界 f[0][j] = 1，f[i][i] = f[i-1][i]。
答案即 f[n][n]。

long long f[45][45];
void catalan2() {
    for (int i = 1; i <= 36; ++i) f[0][i] = 1;
    for (int i = 1; i < 36; ++i)
        for (int j = i; j <= 36; ++j)
            f[i][j] = (i == j) ? f[i-1][j] : f[i-1][j] + f[i][j-1];
}

完整代碼

#include 
long long h[45], f[45][45];

void catalan() {
    h[0] = 1;
    for (int i = 1; i < 36; ++i) {
        h[i] = 0;
        for (int j = 0; j <= i; ++j) h[i] += h[j] * h[i-j-1];
    }
}
void catalan2() {
    for (int i = 1; i <= 36; ++i) f[0][i] = 1;
    for (int i = 1; i < 36; ++i)
        for (int j = i; j <= 36; ++j)
            f[i][j] = (i == j) ? f[i-1][j] : f[i-1][j] + f[i][j-1];
}

int main() {
    catalan(); catalan2();
    int n, cas = 1;
    while (scanf("%d", &n) == 1 && n != -1) {
        printf("%d %d %lld\n", cas++, n, f[n][n] * 2);
    }
    return 0;
}

複雜度與數據範圍

• n ≤ 35，C₃₅ ≈ 3.1e19，需 64 位無符號（unsigned long long）或 %lld（有符號長長整型足夠，C₃₅ < 2⁶³）。
• 預計算 O(n²) ≈ 1200 次操作，查詢 O(1)。

卡特蘭數常見應用

• 合法括號序列數
• 二叉樹形態數
• 凸多邊形三角剖分數
• 棧排列合法出棧序列數
• 不超過對角線的格路數

總結

HDU 2067 是卡特蘭數最直接的應用題。掌握兩種 DP 計算方式（遞歸定義式、網格幾何式），理解 2*Cₙ 的輸出含義，即可輕松解決。n≤35 適合預計算表查詢，避免大數組合數溢出或精度問題。