编辑代码

#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // 定义一个动规数组
        int Max = amount+100;  // 定义一个最大值
        vector<int> dp(amount+1, Max);  // 将动规数组初始化为Max
        dp[0] = 0;  // 所有可兑换的金额都是从dp[0]转化而来的，dp[0]须设为0
        // 逐步增大背包大小
        for(int i=0; i<=amount; i++){
            // 尝试加入不同的硬币
            for(int j=0; j<coins.size(); j++){
                // 当i-coins[i]>=0时，则金额i可能从dp[i-coins[i]]转化而来
                if(i-coins[j] >= 0){
                    int index = i-coins[j];
                    dp[i] = dp[index]+1 < dp[i] ? dp[index]+1 : dp[i] ;
                }
            }
        }
        return dp[amount]>amount ? -1 : dp[amount];
    }
};
int main(){
    int amount =0;
    vector<int> coins= {2,3};
    Solution S;
    int r = S.coinChange(coins, amount);
    cout<<"最少使用的硬币数量为："<<r<<endl;
    system("pause");
    return 0;
}