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