C語言動態規劃解決「撈魚問題」：組合數學與狀態轉移

撈魚問題：20 桶 10 條魚，抓 180 條有多少種方案？

原問題：20 個桶每桶 10 條魚，每桶抓一次，隨機抓取數量，求抓滿 180 條的方案數。

對偶轉化

抓 180 條 ⇔ 剩 20 條。問題等價於：將 20 條魚分配到 20 個桶，每桶 0~10 條，有多少種分配方法？

動態規劃建模

狀態定義：dp[i][j] = 前 i 個桶放 j 條魚的方法數

初始狀態：dp[1][k] = 1 (0 ≤ k ≤ 10)

轉移方程：

dp[i][j] = Σ dp[i-1][j-k]   (0 ≤ k ≤ 10 且 j-k ≥ 0)

自底向上實現

void CatchFish() {
    int dp[21][200] = {0};
    int bucketN = 20, fishN = 20;  // 對偶問題：20桶分20魚

    // 初始化第1個桶
    for (int i = 0; i <= 10; ++i) dp[1][i] = 1;

    // 填表
    for (int i = 2; i <= bucketN; ++i) {
        for (int j = 0; j <= fishN; ++j) {
            for (int k = 0; k <= 10 && j-k >= 0; ++k) {
                dp[i][j] += dp[i-1][j-k];
            }
        }
    }
    printf("%d\n", dp[bucketN][fishN]);
}

複雜度與優化

• 時間：O(桶數 × 魚數 × 最大容量) = 20 × 20 × 11 = 4400 次操作
• 空間：O(桶數 × 魚數) = 400 整數，可優化為滾動數組 O(魚數)
• 結果：89,434,525,395 種方案（需 64 位整數存儲）

遞歸 + 備忘錄對比

自頂向下遞歸同樣正確，但函數調用開銷大，DP 迭代更高效。本質是有放回的有限容量組合數問題，也可用生成函數求解。

擴展思考

• 若桶容量不一致，修改 k 的上限即可
• 若求具體方案，需記錄決策路徑
• 大規模問題可用矩陣快速冪或多項式乘法（NTT）優化