ZeroJudge 解題筆記：d133. 00357 - Let Me Count The Ways

作者：王一哲
日期：2026年4月20日


ZeroJudge 題目連結：d133. 00357 - Let Me Count The Ways

解題想法

因為每種面額的硬幣數量不限，可以取任意數量組成目標金額，是無限背包問題，用動態規畫解題。假設 $dp[i]$ 代表總金額為 $i$ 的組合方式，初始值為 $dp[0] = 1$，總金額 $0$ 只有 $1$ 種組合方式。用一層 for 迴圈依序取出各種面額 $coin$，再用一層 for 迴圈，依序更新 $i = coin$ 到 $i = 30000$ 的方法數，狀態轉移方式為 $dp[i] += dp[i-coin]$。建完 $i = 0$ 到 $i = 30000$ 的方法數表格之後，依序讀取測資、查表、輸出對應的答案。由於這題的方法數有點多，如果用 C 或 C++ 解題，$dp$ 表格要用 long，如果用 int 會溢位。

Python 程式碼

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

def solve():
    import sys

    maxn = 30000
    dp = [0]*(maxn + 1)
    dp[0] = 1
    for coin in (1, 5, 10, 25, 50):
        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
        m = dp[n]
        if m == 1:
            result.append(f"There is only 1 way to produce {n:d} cents change.\n")
        else:
            result.append(f"There are {m:d} ways to produce {n:d} cents change.\n")

    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

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

#include <cstdio>

int main() {
    long dp[30001] = {0};
    dp[0] = 1;
    int coins[5] = {1, 5, 10, 25, 50};
    for(int i=0; i<5; i++) {
        int coin = coins[i];
        for(int j=coin; j<=30000; j++) {
            dp[j] += dp[j - coin];
        }
    }
    
    int n;
    while(scanf("%d", &n) != EOF) {
        long m = dp[n];
        if (m == 1) {
            printf("There is only 1 way to produce %d cents change.\n", n);
        } else {
            printf("There are %ld ways to produce %d cents change.\n", m, n);
        }
    }
    return 0;
}