HDU 1398 Square Coins：母函數求硬幣組合數

題目

硬幣面值為 1², 2², ..., 17² (289)。求湊成 n (n≤300) 的方法數，每種硬幣無限用。輸入多組 n，以 0 結束。

母函數 / 完全背包 DP

dp[i] 表示湊成 i 的方法數。初始 dp[0]=1。對每個硬幣 c，對 i 從 c 到 n：dp[i] += dp[i-c]。因硬幣數固定 (17 種)，n≤300，直接雙層循環即可。注意結果可能大，用 long long。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    const int coins[] = {0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289};
    long long dp[301];
    while (true) {
        int n; if (!(cin >> n)) break; if (n == 0) break;
        fill(dp, dp+n+1, 0);
        dp[0] = 1;
        for (int i = 1; i <= 17; i++) {
            int c = coins[i];
            if (c > n) break;
            for (int j = c; j <= n; j++)
                dp[j] += dp[j-c];
        }
        cout << dp[n] << endl;
    }
    return 0;
}