ZeroJudge 解題筆記：d253. 00674 - Coin Change

作者：王一哲
日期：2026年5月14日


ZeroJudge 題目連結：d253. 00674 - Coin Change

解題想法

每種面額的硬幣使用數量不限，是無限背包問題，用動態規畫解題，假設 $dp[i]$ 是總金額 i 的組合數，初始值是 $dp[0] = 1$。先建表，計算總金額 0 到 7489 的組合數，再讀取測資、查表、輸出答案。

Python 程式碼

使用時間約為 12 ms，記憶體約為 9.9 MB，通過測試。

def solve():
    import sys

    coins = (1, 5, 10, 25, 50)  # 硬幣面額
    maxn = 7489
    dp = [0]*(maxn + 1)  # 總金額 i 有幾種組合
    dp[0] = 1  # 初始值，金額 0 只有 1 種組合
    for coin in coins:  # 無限背包問題
        for i in range(coin, maxn + 1):
            dp[i] += dp[i - coin]
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        result.append(f"{dp[n]:d}\n")
    
    sys.stdout.write("".join(result))
    
if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 3 ms，記憶體約為 1.6 MB，通過測試。

#include <cstdio>

int main() {
    int coins[5] = {1, 5, 10, 25, 50};
    int dp[7490] = {0};
    dp[0] = 1;
    for(int i=0; i<5; i++) {
        int coin = coins[i];
        for(int j=coin; j<=7489; j++) {
            dp[j] += dp[j-coin];
        }
    }
    int n;
    while(scanf("%d", &n) != EOF) {
        printf("%d\n", dp[n]);
    }
    return 0;
}