Coin Change Problem: A Dynamic Programming Approach

The "Coin Change" problem is a notable problem in the field of dynamic programming. It involves finding the minimum number of coins needed to make a specific amount of money, given an array of coin denominations.

Problem Statement

Given an array coins representing different coin denominations and an integer amount, the goal is to find the fewest number of coins needed to make up the given amount. If it's not possible to make up the amount with the given coins, return -1.

Examples

• Input: coins = [1, 2, 5], amount = 11 Output: 3 Explanation: The amount 11 can be composed by 5 + 5 + 1, hence 3 coins.

• Input: coins = [2], amount = 3 Output: -1

JavaScript Solution

function coinChange(coins, amount) {
  const max = amount + 1;
  const dp = new Array(max).fill(max);
  dp[0] = 0;

  for (let i = 1; i <= amount; i++) {
    for (let j = 0; j < coins.length; j++) {
      if (coins[j] <= i) {
        dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
      }
    }
  }

  return dp[amount] > amount ? -1 : dp[amount];
}

Breaking Down the Solution

• Initialize dp Array: Create an array dp of size amount + 1, initializing all elements to amount + 1, except for dp[0], which is set to 0. This initialization prepares the array to store the minimum number of coins required for each amount up to the given amount.

• Dynamic Programming Iteration: Iterate through each amount from 1 to amount. In each iteration, also iterate through the available coin denominations. The goal is to find the minimum number of coins needed for each specific amount.

• Updating the dp Array: For each coin denomination that is less than or equal to the current amount being considered, update dp[i]. Set it to the minimum of its current value and the value calculated for i - coins[j] (the current amount minus the coin denomination) plus one. This step involves comparing and selecting the best option among the previously computed values.

• Return Result: After completing the iterations, check the value of dp[amount]. If it is greater than amount, it implies that it's not possible to make up the amount with the given coins, and the function should return -1. If it's not greater than amount, return dp[amount], which represents the minimum number of coins needed.

Let's explain the "Coin Change" problem in a way that's easy for a 10-year-old to understand.

Imagine you have a piggy bank full of coins of different values - like 1 cent, 5 cents, or 10 cents - and you want to buy a toy that costs a certain amount of money, say 11 cents. Now, the challenge is to find the smallest number of coins you can use to make exactly 11 cents.

It's like a puzzle! You try different combinations of coins to see which one gives you 11 cents using the least number of coins.

Here’s how you might solve it:

Start With No Coins: Think of starting with no coins and then adding one coin at a time to see how many ways you can reach the total amount you need.

Add Coins One by One:

First, see if you can make 1 cent, then 2 cents, and so on, all the way up to 11 cents. For each amount, check all the different coins you could use. For example, to make 4 cents, you could use four 1-cent coins or two 2-cent coins. Keep Track of the Best Way:

For each amount, you keep track of the smallest number of coins needed. You write down the best way to make each amount, like a cheat sheet. So, when you want to make 6 cents, you look back at your cheat sheet to see the best ways to make smaller amounts like 5 cents, 4 cents, etc., and then add one more coin. Find the Smallest Number of Coins for Your Toy:

Once you reach the amount that the toy costs, look at your cheat sheet. The number you wrote down for the toy's cost is the smallest number of coins you can use to buy it. Think of it like a game where you try to score exactly 11 points, and each coin is worth different points. You want to score exactly, and you want to use the fewest turns (or coins) possible to win!

This is what computers do in the "Coin Change" problem – they try all combinations in a smart way to find the answer using the fewest coins.

Conclusion

The "Coin Change" problem effectively demonstrates the power of dynamic programming in solving problems involving the search for optimal combinations. By incrementally building up the solution for increasing amounts and efficiently utilizing previously computed results, this approach provides an elegant and efficient solution to the problem, emphasizing the importance of identifying and optimizing overlapping subproblems.