HDU 2067 卡特蘭數經典應用：不穿越對角線的棋盤路徑計數

HDU 2067 卡特蘭數經典應用：不穿越對角線的棋盤路徑計數

題目要求：從 (0,0) 走到 (n,n)，只能向右/向上移動，路徑不穿越對角線 y=x（可接觸）。這是卡特蘭數 經典模型，答案為第 n 個卡特蘭數 C(2n,n)/(n+1)，本題輸出為 2 * Catalan(n)（因題目路徑包含對角線兩側對稱）。

數學推導

• 總路徑數：C(2n, n)（2n 步中選 n 步向右）。
• 非法路徑（穿越對角線）：利用反射原理，與從 (-1,1) 到 (n,n) 的路徑一一對應，數為 C(2n, n+1)。
• 合法路徑（單側）：C(2n,n) - C(2n,n+1) = C(2n,n)/(n+1) = Catalan(n)。
• 本題允許接觸對角線且兩側對稱，故答案 2 * Catalan(n)。

動態規劃遞推實現（避免大數組合數溢出）

#include 
#define LL long long

LL num[36][36] = {0};

void init() {
    for (int i = 1; i <= 35; i++) {
        num[i][0] = 1;
        for (int j = 1; j < i; j++)
            num[i][j] = num[i][j-1] + num[i-1][j];
        num[i][i] = num[i][i-1]; // 對角線值等於左側值
    }
}

int main() {
    init();
    int n, ca = 1;
    while (scanf("%d", &n) != EOF) {
        if (n == -1) break;
        printf("%d %d %lld\n", ca++, n, 2 * num[n][n]);
    }
    return 0;
}

遞推關係解析

num[i][j] 表示從 (0,0) 到 (i,j) 不超過對角線的路徑數。遞推：num[i][j] = num[i][j-1] + num[i-1][j]（來自左/下），邊界 num[i][0]=1，對角線 num[i][i]=num[i][i-1]（不能從右上來）。

空間優化版（一維數組）

int main() {
    LL a[36] = {1}, b[36] = {0};
    for (int i=1; i<36; i++) {
        for (int j=1; j

關鍵點總結

識別卡特蘭數模型是解題關鍵，常見於棧出棧序列、二叉樹計數、括號匹配、不越界路徑。
n ≤ 35，Catalan(35) 約 3×10^18，需 64 位整數（long long / __int64）。
DP 遞推比組合數公式更穩健，避免中間階乘溢出與除法精度問題。
輸出格式嚴格：案例編號、n、結果，空格分隔。