题解 | #兑换零钱#

#include <bits/stdc++.h>

using namespace std;
 


int main()
{
    int n,aim;
    scanf("%d %d\n",&n,&aim);
    vector<int> dp(aim+1,INT_MAX-1);
    dp[0] = 0;
    for(int i=0;i<n;i++) {
        int item;
        scanf("%d",&item);
        for(int j=item;j<=aim;j++)
            dp[j] = min(dp[j],dp[j-item]+1);
    } 
    printf("%d\n",dp[aim]==INT_MAX-1? -1:dp[aim]);

    return 0;
}