题解 | 兑换零钱

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

int main() {
    int n, aim;
    cin >> n >> aim;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    const int INF = 1e9;
    vector<int> dp(aim + 1, INF);
    dp[0] = 0;

    // 完全背包：每种面值可用任意张
    for (int v : a) {
        if (v > aim) continue;
        for (int s = v; s <= aim; ++s) {
            dp[s] = min(dp[s], dp[s - v] + 1);
        }
    }

    cout << (dp[aim] >= INF ? -1 : dp[aim]) << '\n';
    return 0;
}