HDU 1398 Square Coins 題解：母函數/動態規劃求硬幣組合數

題目大意

銀幣面值為平方數：1, 4, 9, ..., 289 (17^2)。給定金額 n (< 300)，求湊成該金額的硬幣組合數（順序無關）。多測試用例，以 0 結束。

解題思路：母函數 / 完全背包變體

每種面值硬幣可無限使用。令 s[i] 表示湊成金額 i 的方案數。初始 s[0] = 1，其餘 0。對每種面值 v = k*k (k=1..17)，更新：

for (int i = 0; i <= n; i++) a[i] = 0;
for (int j = 0; j <= n; j++)
    for (int k = 0; k + j <= n; k += v)
        a[k + j] += s[j];
for (int i = 0; i <= n; i++) { s[i] = a[i]; a[i] = 0; }

最終 s[n] 即為答案。本質是生成函數係數計算，等價於完全背包 DP。

AC 代碼 (C)

#include <stdio.h>
int a[310], s[310];
int main() {
    int i, j, k, n;
    while (scanf("%d", &n), n) {
        for (i = 0; i <= n; i++) { a[i] = 0; s[i] = 1; }
        for (i = 2; i <= n; i++) {
            for (j = 0; j <= n; j++) {
                for (k = 0; k + j <= n; k += i * i)
                    a[k + j] += s[j];
            }
            for (j = 0; j <= n; j++) { s[j] = a[j]; a[j] = 0; }
        }
        printf("%d\n", s[n]);
    }
    return 0;
}

注意：外層循環 i 從 2 開始對應面值 4，初始 s[i]=1 已包含面值 1 的貢獻。