藍橋杯「未名湖的煩惱」遞歸算法深度解析

問題背景

經典組合數學問題：m 個還鞋、n 個借鞋排隊，任意前綴還鞋數 ≥ 借鞋數，求合法排隊數。

遞歸函數含義

int fun(int m, int n) {
    if (m < n) return 0;      // 非法：借鞋超過還鞋
    if (n == 0) return 1;     // 邊界：無借鞋者，只有1種全還鞋
    return fun(m-1, n) + fun(m, n-1);
}

組合意義拆解

• fun(m-1, n)：隊首是還鞋者 → 剩餘 m-1 還、n 借的合法排列數
• fun(m, n-1)：隊首是借鞋者 → 剩餘 m 還、n-1 借的合法排列數
• 兩種互斥情況覆蓋所有合法排列

數學本質

這是 卡特蘭數 變體：C(m+n, n) - C(m+n, n-1) 或 (m-n+1)/(m+1) * C(m+n, n)。

優化方向

1. 記憶化遞歸：dp[m][n] 存儲中間結果，O(mn)
2. 動態規劃底-up：雙層循環填表
3. 組合公式直接計算：預處理階乘+模逆元，O(1) 查詢

測試用例

fun(3,2)=5，對應序列：HHHKK, HHKHK, HHKKH, HKHHK, HKHKH (H=還，K=借)。