UVA 10313 Pay the Price：硬幣找零組合數 DP（完全背包變體）

題目大意

有面值 1~300 的硬幣各無限枚。輸入三種模式查詢：

1. n：組成金額 n 的方案數
2. n a：用不超過 a 枚硬幣組成 n 的方案數
3. n a b：用硬幣數在 [a, b] 之間組成 n 的方案數

核心結論：整數分拆對偶性

用不超過 k 個正整數分拆 n 的方案數 = 用最大值不超過 k 的正整數分拆 n 的方案數（Ferrers 圖轉置）。

因此 dp[i][j] 定義為：用面值 ≤ j 的硬幣組成金額 i 的方案數（等價於用 ≤ j 枚硬幣）。

狀態轉移

dp[0][0] = 1;
for i = 1..300:
    for j = 1..300:
        if i >= j:
            dp[i][j] = dp[i-j][j] + dp[i][j-1]; // 用面值 j / 不用面值 j
        else:
            dp[i][j] = dp[i][j-1]; // 面值 j 太大不可用

查詢回答

• 單參數 n → dp[n][n]
• 雙參數 n a → dp[n][min(a,300)]
• 三參數 n a b → dp[n][min(b,300)] - dp[n][min(a-1,300)]（a=0 時直接 dp[n][b]）

完整代碼

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;

ll dp[305][305];

void init() {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 0; i <= 300; ++i) {
        for (int j = 1; j <= 300; ++j) {
            if (i >= j) dp[i][j] = dp[i-j][j] + dp[i][j-1];
            else dp[i][j] = dp[i][j-1];
        }
    }
}

int main() {
    init();
    int n, a, b;
    while (scanf("%d", &n) != EOF) {
        char ch; a = 1; b = n;
        scanf("%c", &ch);
        int flag = 0;
        if (ch == ' ') {
            flag = 1;
            scanf("%d", &a);
            scanf("%c", &ch);
            if (ch == ' ') { flag = 2; scanf("%d", &b); }
        }
        a = min(a, 300); b = min(b, 300);
        ll ans;
        if (!flag) ans = dp[n][n];
        else if (flag == 1) ans = dp[n][a];
        else { // flag == 2
            if (a == 0) ans = dp[n][b];
            else ans = dp[n][b] - dp[n][a-1];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

複雜度

• 預處理：O(300²) ≈ 9e4
• 查詢：O(1)
• 空間：O(300²)