UVA 674 Coin Change：完全背包求硬幣組合數

題目大意

• 硬幣面值：1, 5, 10, 25, 50 美分。
• 查詢金額 `n ≤ 7489`，求組合數（順序不重要，每種硬幣無限用）。
• 多查詢，以 EOF 結束。

DP 定義與轉移

dp[i][j]：用前 `j` 種硬幣組成金額 `i` 的方案數。
轉移：`dp[i][j] = dp[i][j-1] + dp[i-coin[j]][j]`（不選第 j 種 + 至少選一個第 j 種）。
初始：`dp[0][j] = 1`（金額 0 有 1 種方案），`dp[i][0] = 0 (i>0)`。

一維優化

外層循環硬幣，內層循環金額**正序**：

dp[0] = 1;
for (int c : coins)
    for (int i = c; i <= MAXN; ++i)
        dp[i] += dp[i - c];

完整代碼

#include 
using namespace std;
const int MAXN = 7490;
int coins[5] = {1, 5, 10, 25, 50};
int dp[MAXN + 1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    dp[0] = 1;
    for (int c : coins)
        for (int i = c; i <= MAXN; ++i)
            dp[i] += dp[i - c];
    int n;
    while (cin >> n) cout << dp[n] << "\n";
    return 0;
}

複雜度

• 預處理 O(5 × 7490) ≈ 3.7e4。
• 查詢 O(1)。