357 Let Me Count The Ways

題目連結

題目敘述

在一家大型百貨公司購物後，Mel 找零 17 分
他收到 1 枚 10 分硬幣、1 枚 5 分硬幣，以及 2 枚 1 分硬幣
當天稍晚，他又在便利商店購物，再次找零 17 分
這次他收到 2 枚 5 分硬幣和 7 枚 1 分硬幣
他開始想：「我可以在幾家商店買東西，並以不同的硬幣組合收到 17 分的找零？」經過一番腦力激盪後，他認為答案是 6
於是他挑戰你思考這個更廣泛的問題

撰寫一個程式，來計算用美國硬幣（1 分、5 分、10 分、25 分、50 分）湊出某金額的所有不同組合方式的數量

輸入格式

輸入為一組數字，每行一個，範圍為 0 到 30000（含）之間

輸出格式

對於輸入的每一個數字，輸出以下陳述中適合的一句，每行輸出一筆
變數 m 為你的程式計算出的方式數，n 為輸入的金額數值
根據方法數進行兩種格式的輸出

There are m ways to produce n cents change.
There is only 1 way to produce n cents change.

輸入說明

輸入檔案包含任意行，每一行都是一個整數，代表金額（單位為分）

輸出說明

對於輸入的每一行，輸出一行，顯示使用上述五種硬幣找零的不同方式總數

解題思路

本題可視為一維的「完全背包」或「計數型背包」

定義一維狀態 dp[x]：代表「湊出金額 x 的不同組合數」
初始：dp 全部為 1，意即「不取任何硬幣」也是一種合法方式
對於每種面額 c，透過 dp[x] += dp[x−c]
將「少一枚 c 分的湊法」累加到「當前湊法」上

固定「先處理某一面額，再處理下一面額」的步驟，能確保同一組合（例如「10+1」和「1+10」）不會被重複計算
一旦把所有面額都「加入」過一次，dp[n] 就涵蓋了以任意次數、任意組合取用這些硬幣所得的所有可能

記得要加 define int long long

程式碼

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main() {
    int n;
    vector<int> dp(30005, 1), a = {5, 10, 25, 50};
    for (auto &c : a) for (int i = c; i < 30005; i++) dp[i] += dp[i-c];
    while (cin >> n) {
        if (dp[n] == 1) cout << "There is only 1 way to produce " << n << " cents change.\n";
        else cout << "There are " << dp[n] << " ways to produce " << n << " cents change.\n";
    }
}