```
class Solution {
public:
int coinChange(vector<int>& coins, int amount)
{
if (coins.empty()) return 0;
vector<int> DP(amount + 1, INT_MAX-1);
DP[0] = 0;
for (int i = 0; i < coins.size(); i++)
{
for (int j = coins[i]; j <= amount; j++)
{
DP[j] = min(DP[j], DP[j-coins[i]] + 1);
}
}
if (DP[amount] < INT_MAX-1) return DP[amount];
else return -1;
}
};
```