雞蛋放入籃子的分法計算：遞歸解法與經典整數分拆問題

雞蛋放入籃子的分法計算：遞歸解法與經典整數分拆問題

給定 n 個相同的雞蛋放入 m 個相同的籃子，允許籃子為空，求不同的放法數。注意：2,1,1 和 1,2,1 視為同一種分法（順序不重要）。這是典型的「整數分拆」問題，即將整數 n 分拆為不超過 m 個正整數之和的方案數。

遞歸思路

定義 egg(m, n) 為將 n 個雞蛋放入 m 個籃子的方案數。考慮最後一個籃子的狀態：

• 若 m == 1 或 n == 0：只有 1 種放法（全放入唯一籃子或無蛋可放）。
• 若 n < 0：方案數為 0。
• 一般情況：兩種互斥情況相加：
  1. 至少有一個籃子為空 → 等價於將 n 個蛋放入 m-1 個籃子：egg(m-1, n)
  2. 每個籃子至少有一個蛋 → 先每個籃子放 1 個，剩下 n-m 個蛋繼續放入 m 個籃子：egg(m, n-m)

遞歸關係式：egg(m, n) = egg(m-1, n) + egg(m, n-m)，配合邊界條件即可求解。

參考代碼

#include <stdio.h>

int egg(int m, int n);

int main() {
    int t, m, n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &m, &n);
        printf("%d\n", egg(m, n));
    }
    return 0;
}

int egg(int m, int n) {
    if (m == 1 || n == 0) return 1;
    if (n < 0) return 0;
    return egg(m - 1, n) + egg(m, n - m);
}

測試範例

輸入：

4
3 8
4 7
2 4
4 2

輸出：

10
11
3
2

複雜度與優化

直接遞歸存在大量重複計算，可引入備忘錄（二維陣列 dp[m+1][n+1]）或採用動態規劃自底向上填表，將時間複雜度從指數級降至 O(m*n)。由於題目限制 m,n ≤ 10，遞歸仍可在時限內通過，但建議練習 DP 寫法以應對更大規模輸入。