The intuition here is that to form a change for an amount (say X) and lets say we have coins of denomination {1, 2, 5}. We could have formed this change X from X-1 and then adding the coin of value 1 or from X-2 and adding a coin of value 2 or from X-5 and then adding the coin of value 5. Take a max over these to find the optimal solution. If coins is the vector/array of denominations of coins, more formally,

N = Number of elements in coins

OPT(x) = max(OPT(x - coins[k]) + 1) where k <- 0 to N

with base conditions,

OPT(0) = 0

OPT(x) = -1 if N == 0

```
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
if(n == 0) return -1;//cannot make change with 0 coins
if(amount == 0) return 0;//can always make change without any coins
int dp[amount+1];
dp[0] = 0;//base case: when amount = 0
for(int amt = 1; amt <= amount; amt++){
dp[amt] = -1;
for(int i = 0; i < n; i++){
if(amt - coins[i] >= 0 && dp[amt-coins[i]] != -1){
if(dp[amt] == -1) dp[amt] = dp[amt-coins[i]]+1;
else dp[amt] = min(dp[amt], dp[amt-coins[i]]+1);
}
}
}
return dp[amount];
}
};
```