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

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

題目大意

硬幣面額 {1, 5, 10, 25, 50}，每種無限枚。查詢金額 n (≤7489) 的組合數。多查詢，至 EOF。

完全背包 DP

dp[v] 表示湊出金額 v 的方案數。對每種硬幣，正序遍歷金額累加：

dp[0] = 1;
for (int c : {1,5,10,25,50})
    for (int v = c; v <= 7489; ++v)
        dp[v] += dp[v - c];

正序遍歷保證同一硬幣可重複使用（完全背包特徵）。預計算後 O(1) 回答查詢。

完整代碼

#include 
#include 
#define MAXN 7500

int dp[MAXN];
int coins[] = {1, 5, 10, 25, 50};

int main() {
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for (int c : coins)
        for (int v = c; v < MAXN; ++v)
            dp[v] += dp[v - c];

    int n;
    while (~scanf("%d", &n))
        printf("%d\n", dp[n]);
    return 0;
}

複雜度

• 預處理：O(5 × 7489) ≈ 3.7 萬次操作，極快
• 查詢：O(1)
• 空間：O(7489)

此題是完全背包「求方案數」最基礎的模板題，掌握正序遍歷即可舉一反三。