C++ DP with detailed explanation

• 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];
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.