方法一

参考动态规划的意义是什么？ - 阮行止的回答中1. 从一个生活问题谈起的思路。

#include<iostream>
#include<vector>

using namespace std;

int getMinCoin(vector<int>& arr, int aim){
    if(arr.empty() || aim<0){
        return -1;
    }
    else if(aim==0)
        return 0;
    int n=arr.size();
    //记录凑出0～aim元时，需要的最少货币数。
    //INT16_MAX表示凑不出来
    vector<int> dp(aim+1,INT16_MAX);
    dp[0]=0;//凑出0元，货币数是0
    for(int i=1;i<=aim;i++){
        for(int j=0;j<n;j++){
            //i-arr[j]>=0.表示当前货币i可以使用arr[j]换
            if((i-arr[j])>=0) {
                //dp[i-arr[j]]表示换了后的剩余货币数
                //想象成dp[i-arr[j]]已是最优解，
                //则换i元所需的货币数为i-arr[j]所需货币数+1
                dp[i] = min(dp[i],dp[i-arr[j]]+1);
            }               
        }
    }
    //说明给定的货币都换不出来
    if(dp[aim]==INT16_MAX)
        return -1;
    return dp[aim];    
}

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

    auto res=getMinCoin(arr,aim);
    cout<<res<<endl;
    return 0;
}

方法二

根据左程云书中原问题的经典动态规划方法。

#include<iostream>
#include<vector>

using namespace std;

//使用二维dp矩阵的解法
int getMinCoin(vector<int>& arr, int aim) {
    if (arr.empty() || aim < 0) {
        return -1;
    } else if (aim == 0)
        return 0;
    int n = arr.size(); //货币的种类数

    vector<vector<int>> dp(n,vector<int>(aim+1));
    //只使用dp[0]货币时，记录凑出0～aim元时，
    //需要的最少货币数，存入dp[0][j]。
    //INT16_MAX表示凑不出
    int maxV=INT16_MAX;
    for(int j=1;j<(aim+1);j++){
        dp[0][j]=maxV;
        //j-arr[0]>=0，表示当前价值j可以使用arr[0]凑
        //dp[0][j-arr[0]]!=INT16_MAX，表示使用arr[0]能凑出j-arr[0]
        if((j-arr[0])>=0 && dp[0][j-arr[0]]!=maxV){
            //只需在dp[0][j-arr[0]]使用的货币数上加1
            dp[0][j]=dp[0][j-arr[0]]+1;
        }
    }

    int cost=0;
    for (int i = 1; i < n; i++) {
        //由于dp[i][0]表示aim=0时需要的货币数，因此全为0。
        //所以j从1开始

        for (int j = 1; j < (aim+1); j++) {
            cost=maxV;
            if((j-arr[i])>=0 && dp[i][j-arr[i]]!=maxV){
                //cost表示使用了一个arr[i]货币，换出j价值所需的货币数
                cost=dp[i][j-arr[i]]+1;
            }
            //dp[i-1][j]表示不使用arr[i]货币时，换出j价值所需的货币数
            //当不用arr[i]货币就能换出j价值货币时，
            //所需的货币数小于使用了的，则不用arr[i]货币
            dp[i][j]=min(dp[i-1][j],cost);
        }
    }
    //说明给定的货币都换不出来
    if (dp[n-1][aim] == maxV)
        return -1;
    return dp[n-1][aim];
}

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

    auto res = getMinCoin(arr, aim);
    cout << res << endl;
    return 0;
}

方法三

根据左程云书中原问题在动态规划基础上的空间压缩方法。

#include<iostream>
#include<vector>

using namespace std;

//使用一维dp矩阵的解法
int getMinCoin(vector<int>& arr, int aim) {
    if (arr.empty() || aim < 0) {
        return -1;
    } else if (aim == 0)
        return 0;
    int n = arr.size(); //货币的种类数

    //对dp进行滚动更新，起始时dp[j]代表只使用arr[0]货币时，
    //记录凑出j元时，需要的最少货币数。
    //终止时，dp[j]代表使用了arr[0～n-1]货币凑出j元时,需要的最少货币数。
    vector<int> dp(aim+1);
    //INT16_MAX表示凑不出
    int maxV=INT16_MAX;
    for(int j=1;j<(aim+1);j++){
        dp[j]=maxV;
        //j-arr[0]>=0，表示当前价值j可以使用arr[0]凑
        //dp[j-arr[0]]!=INT16_MAX，表示使用arr[0]能凑出j-arr[0]
        if((j-arr[0])>=0 && dp[j-arr[0]]!=maxV){
            //只需在dp[j-arr[0]]使用的货币数上加1
            dp[j]=dp[j-arr[0]]+1;
        }
    }

    int cost=0;
    for (int i = 1; i < n; i++) {
        //由于dp[0]表示aim=0时需要的货币数，因此全为0。
        //所以j从1开始       
        for (int j = 1; j < (aim+1); j++) {
            cost=maxV;
            if((j-arr[i])>=0 && dp[j-arr[i]]!=maxV){
                //cost表示使用了一个arr[i]货币，换出j价值所需的货币数
                cost=dp[j-arr[i]]+1;
            }
            //右侧的dp[j]未更新，表示不使用arr[i]货币时，换出j价值所需的货币数
            //当不用arr[i]货币就能换出j价值货币时，
            //所需的货币数小于使用了的，则不用arr[i]货币
            dp[j]=min(dp[j],cost);
        }
    }
    //说明给定的货币都换不出来
    if (dp[aim] == maxV)
        return -1;
    return dp[aim];
}

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

    auto res = getMinCoin(arr, aim);
    cout << res << endl;
    return 0;
}