题解 | 兑换零钱

#include <climits>
#include <iostream>
#include <vector>
using namespace std;
//类似完全背包问题
int main() {
    int n,aim;
    cin>>n>>aim;
    vector<int> arr(n,0);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    vector<int> dp(aim+1,INT_MAX);//dp[i]表示组成钱数i所需的最少货币数
    dp[0]=0;
    for(int i=1;i<aim+1;i++){
        for(int j=0;j<n;j++){
            if(arr[j]<=i){
                dp[i]=min(dp[i-arr[j]]+1,dp[i]);
            }
        }
    }
    cout<<(dp[aim]==INT_MAX?-1:dp[aim]);
    return 0;
}
// 64 位输出请用 printf("%lld")