The min-coin change problem can also be resolved with a greedy algorithm. Most of the time, the result is also optimal, but for some denominations, the result will not be optimal.
Let's take a look at the algorithm:
function minCoinChange(coins, amount) { const change = []; let total = 0; for (let i = coins.length; i >= 0; i--) { // {1} const coin = coins[i]; while (total + coin <= amount) { // {2} change.push(coin); // {3} total += coin; // {4} } } return change;}
Note that the greedy version of minCoinChange is much simpler than the DP one. For each coin ({1}, starting from the biggest one to the smallest one), we will add the coin value to total, and total needs to be less than amount ({2}). We will add coin ...
