Suppose we have coins = `{ 1 , 2 , 5 , 10...M}`

, index = `0 , 1 , 2 , 3...j`

.

Consider the last coin[j] = `M`

, we either use it at least once or don't use it at all,

if we use it at least once, the amount of money decrease by `M`

, `amount = amount - M`

if we don't use it at all, the amount of money stay the same, but the coin set we use becomes coins = `1 , 2 , 5 , 10...M-1`

; index = `0 , 1 , 2 , 3...j-1`

.

And the min exchange solution must be in either with M or without M.

Therefore, the DP representation would be

`dp[i][j]`

: Use coins indices from `0`

to `j`

to exchange the amount of money `i`

`dp[i][j] = min{ dp[i][j-1], dp[i-coins[j]][j]+1 }`

```
int coinChange(vector<int>& coins, int amount) {
//dp[i][j] = min{ dp[i][j-1], dp[i-coins[j]][j]+1 }
vector<vector<int>>dp(amount+1,coins);
for(int i = 0; i < coins.size(); i++) dp[0][i] = 0;
for(int i = 0; i < amount+1; i++) dp[i][0] = i % coins[0] == 0 ? i / coins[0] : INT_MAX-1;
for(int i = 1; i < amount+1; i++)
for(int j = 1; j < coins.size(); j++)
if(i >= coins[j]) dp[i][j] = min(dp[i][j-1], dp[i-coins[j]][j]+1);
else dp[i][j] = dp[i][j-1];
return dp[amount][coins.size()-1] == INT_MAX-1 ? -1 : dp[amount][coins.size()-1];
}
```