题解 | #兑换零钱#

解题思路：

完全背包下加条件，令 $d p_{j}$ 表示第 $i$ 种钱下，容量为 $j$ 的背包，考虑 $dp_j = 0\ or\ dp_{j-arr_i} = 0$ 情况下状态方程：

dp_j = \min(dp_{j-arr_i}+1, dp_j),(dp_j \neq 0 ,dp_{j+arr_i} \neq 0)

dp_j = (j+arr_i) \div arr_i,(dp_{j-arr_i} = 0,(j+arr_i) \mod arr_i = 0)

dp_j = dp_{j-arr_i}+1,(dp_j = 0, dp_{j-arr_i} \neq 0)

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    int n, aim;
    cin>>n>>aim;
    vector<int> arr(n+1);
    for(int i = 1; i <= n; ++i){
        cin>>arr[i];
    }
    vector<int> dp(aim+1);
    for(int i = 1; i <= n; ++i){
        for(int j = 0; j <= aim - arr[i]; ++j){
        if(dp[j] != 0){
            if(dp[j+arr[i]] == 0) dp[j+arr[i]] = dp[j] +1;
            else dp[j+arr[i]] = min(dp[j]+1,dp[j+arr[i]]);
        } 
        else if((j+arr[i])%arr[i] == 0) dp[j+arr[i]] = (j+arr[i])/arr[i];
        }
    }
    int ans;
    if(dp[aim] > 0 || aim == 0) ans = dp[aim];
    else ans = -1;
    cout<<ans<<endl;
    return 0;
}