HDU 2069 Coin Change：帶硬幣數量限制的母函數求解

問題特點

本題在普通母函數基礎上增加了「組成個數不能超過 100 個硬幣」的限制。這要求我們將一維數組擴展為二維數組 c1[結果][組成個數]，並在遞推過程中增加一層遍歷硬幣個數的循環。

核心算法

const int MAX = 252;
int ans[MAX] = {};
int c1[MAX][MAX], c2[MAX][MAX];  // c1[系數][累加個數]

void getAns() {
    ans[0] = 1;
    const int coins[] = {0, 1, 5, 10, 25, 50};
    
    for (int n = 1; n <= 5; n++) {
        for (int i = 0; i <= 250; i++) {
            for (int j = 0; j <= 100; j++) {
                if (c1[i][j]) {
                    for (int k = 1; k * coins[n] + i <= 250 && j + k <= 100; k++) {
                        c2[i + k * coins[n]][j + k] += c1[i][j];
                    }
                }
            }
        }
        // 複製 c2 到 c1，清空 c2
        memcpy(c1, c2, sizeof(c1));
        memset(c2, 0, sizeof(c2));
    }
    
    for (int i = 0; i <= 250; i++) {
        for (int j = 0; j <= 100; j++) ans[i] += c1[i][j];
    }
}

關鍵點解析

1. 二維狀態設計：c1[金額][硬幣數] 記錄恰好用 j 個硬幣湊出金額 i 的方案數
2. 滾動數組優化：使用 c1、c2 交替存儲，避免開大三維數組
3. 邊界控制：k * coins[n] + i <= 250 && j + k <= 100 確保不越界

複雜度分析

時間：O(硬幣種類 × 最大金額 × 最大硬幣數 × 平均選擇數) ≈ O(5 × 250 × 100 × 50) 可接受
空間：O(250 × 100) × 2 ≈ 50KB