练86.3 货币系统

解题思路

零钱组合计数，dp[0]=1。外层按面值逐种处理，内层金额从coin升序到m，dp[s]+=dp[s-coin]。外层币种顺序固定避免把同组合的不同取钱次序重复计算。

正确性说明

处理当前币种时，不用它的方案已在dp[s]，至少用一枚的方案可由当前轮dp[s-c]再加一枚得到。升序允许重复使用，币种外层保证组合只计一次。

易错点

本题输入格式漏写后续面值，但样例明确需读取n个面值；方案数用字符串大整数防溢出。

复杂度

最大计数D位，时间O(nmD)，空间O(mD)。

参考代码（C++11）

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

string addBig(string a, string b) {
    string s;
    int i = a.size() - 1, j = b.size() - 1, c = 0;
    while (i >= 0 || j >= 0 || c) {
        int v = c;
        if (i >= 0)
            v += a[i--] - '0';
        if (j >= 0)
            v += b[j--] - '0';
        s += char('0' + v % 10);
        c = v / 10;
    }
    while (s.size() > 1 && s.back() == '0')
        s.pop_back();
    reverse(s.begin(), s.end());
    return s;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> coin(n);
    for (int &x : coin)
        cin >> x;
    vector<string> dp(m + 1, "0");
    dp[0] = "1";
    for (int c : coin)
        for (int s = c; s <= m; s++)
            dp[s] = addBig(dp[s], dp[s - c]);
    cout << dp[m] << "\n";
    return 0;
}