一本通-1273：【例9.17】货币系统

【题目描述】 给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。

【输入】 第一行为n和m。

【输出】 一行，方案数。

【输入样例】 3 10 //3种面值组成面值为10的方案 1 //面值1 2 //面值2 5 //面值5

【输出样例】 10 //有10种方案

---

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> seq(10005);
vector<long long> d(10005);

long long completePack()
{
    d[0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = seq[i]; j <= m; ++j) {
            d[j] += d[j - seq[i]];
        }
    }

    return d[m];
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> seq[i];
    cout << completePack() << endl;

    return 0;
}