HDU 2069 Coin Change：硬幣找零的組合數 DP（限制最多 100 枚）

問題重述

給定硬幣面額 {1, 5, 10, 25, 50}，求組成金額 n（n ≤ 250）的方案數。每種硬幣可無限使用，但總硬幣數不超過 100 枚。多組輸入，EOF 結束。

動態規劃設計

二維 DP：dp[i][j] 表示用恰好 j 枚硬幣組成金額 i 的方案數。
初始：dp[0][0] = 1（0 元 0 枚硬幣 1 種方案）。
轉移：對每種硬幣 c，對金額 i 從 c 到 n，對硬幣數 k 從 1 到 100：
dp[i][k] += dp[i - c][k - 1]

最終答案：sum_{k=1}^{100} dp[n][k]。

優化細節

• 金額上限 250，硬幣數上限 100，狀態數 251 × 101 ≈ 2.5 萬，極小。
• 可用滾動數組或原地更新（i 遞增，k 遞增），但注意硬幣無限用，故 i 正序、k 正序即可。
• 結果可能較大，用 long long。

代碼實現 (C++)

#include <bits/stdc++.h>
using namespace std;
const int COINS[5] = {1, 5, 10, 25, 50};
const int MAXN = 250, MAXK = 100;
long long dp[MAXN + 1][MAXK + 1];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    dp[0][0] = 1;
    for (int c : COINS) {
        for (int i = c; i <= MAXN; ++i) {
            for (int k = 1; k <= MAXK; ++k) {
                dp[i][k] += dp[i - c][k - 1];
            }
        }
    }
    // 預計算前綴和 ans[n] = sum_{k=1}^{100} dp[n][k]
    long long ans[MAXN + 1] = {0};
    for (int i = 1; i <= MAXN; ++i) {
        for (int k = 1; k <= MAXK; ++k) ans[i] += dp[i][k];
    }
    int n;
    while (cin >> n) {
        cout << ans[n] << '\n';
    }
    return 0;
}

複雜度

• 預處理：O(5 × 250 × 100) = 125,000 操作。
• 查詢：O(1)。
• 空間：O(250 × 100) ≈ 200 KB。

關鍵點總結

• 「最多 100 枚」轉化為「恰好 k 枚」的二維 DP。
• 完全背包變體：物品無限，但增加「物品數量」維度。
• 預處理所有 n，多查詢極快。

這題是經典「帶個數限制的完全背包」變體，二維 DP 狀態設計清晰，預處理思想適用於多測試用例場景。