问题描述
思路
根据题意，最暴力的方法就是枚举所有的情况，并且是求最值问题，所以就可以想到用动态规划的方法进行求解
代码
class Solution {
public:
int coinChange(vector
<int>& coins
, int amount
) {
int n
=coins
.size();
if(amount
==0) return 0;
if(n
==1&&amount
%coins
[0]!=0) return -1;
if(n
==1&&amount
%coins
[0]==0) return amount
/coins
[0];
vector
<int> dp(amount
+1,INT_MAX
);
dp
[0]=0;
for(int i
=1;i
<=amount
;i
++) {
for(int j
=0;j
<n
;j
++) {
if(i
>=coins
[j
]&&dp
[i
-coins
[j
]]!=-1) dp
[i
]=min(dp
[i
],dp
[i
-coins
[j
]]+1);
}
if(dp
[i
]==INT_MAX
) dp
[i
]=-1;
}
return dp
[amount
];
}
};
