Using Dynamic Programming to Solve Coin Change

What is dynamic programing? Dynamic Programming (DP) is a technique for solving an optimization problem. This is done by breaking down the problem into simpler subproblems and using the solutions to solve the larger problem.

A popular problem is Coin Change. In this problem we are given an array with different coin values, and an integer with our target amount. To solve the problem we need to find the minimum number of coins necessary to reach the target amount.

There are a number of ways to solve this problem, however we are going to walk through the bottom-up dp approach using an example.

Coin Change - LeetCode

In this example we will have the input of 2, 5, and 8 coins and the target amount of 12 (coinChange([2,5,8], 12)).

1. The first step will be to create a dp array where we will track optimal number of coins necessary to reach each target or “currentTarget” (currentTarget = value of the index at that point in the array)

First Step, Setting up the dp array

Start dp array

• Length: This will be of length amount +1 as we start with zero, and in the end we want to know the optimal number of coins to get the “currentTarget” which will be equal to amount
• Values: The dp array will first be filled with a placeholder (must be larger than amount) dp[0] will be 0 as you need zero coins to make “currentTarget” of zero

Full Solution

2. Next we will iterate through the coins. We start with the first coin, and check the optimal number of that coin necessary to reach each currentTarget

• currentTarget will start at the value of the coin and be incremented by one after each calculation (can also look at it as the value of the index at that point in the array)

2a. In our first calculation(#1 on the left), our currentTarget is equal to coin[0] (or 2). We first subtract the coin from the currentTarget to give us our remainder (let remainder = currentTarget-coin[i], 0= 2–2). The remainder is equal to 0. Meaning we only needed one coin to reach the currentTarget. We add dp[0] (which is 0) to 1 (the current coin used), and update the value at dp[currentTarget] or dp[2] to 1.

2b. In our second calculation(#2 on the left), our currentTarget is equal to 3. After subtracting one coin the remainder is one. Therefore we check dp[1] which is equal to Infinity. Therefore we know that it is not possible to reach currentTarget of 3 with the current given coin, and dp[3] will remain as Infinity.

2c. In our third calculation(#3 on the left), our currentTarget is equal to 4. After subtracting one coin the remainder is two. Using dynamic programing we look at our previous calculation to see how many coins we needed to reach that number (dp[2] =1). We add this amount to the one coin we used in the current operation, and update dp[4] to 2.

2b.We follow the same process using coin[0] (or 2) incrementing currentTarget by one until we reach amount.

3. We then do the same for each coin value, however we now have the calculations from our previous coins saved in our dp array available.

Same solution as above but abbreviated

4. Once we have iterated through all of our coins our dp array is complete. We finally can return the optimal solution of coins for the input amount. If dp[amount]=Infinity we know there is no solution and return -1. However if it is not infinity we have a solution!