Solving the Coin Change problem with Dynamic Programming

Justin Dumadag
Mar 31 · 3 min read

Photo by Michael Longmire on Unsplash

First off what is Dynamic programming (DP)? It is a technique or process where you take a complex problem and break it down into smaller easier to solve sub-problems and building it back up. You would solve the easier sub-problems then store their solutions to be used again.

It optimized everyone’s favorite topic : recursion. If you ever see a recursion problem that has repeated calls for the same input we can use DP for optimization. Again, you would store the results of the sub-problem so you don’t have to calculate it at again when it is needed.

Let me quickly give you an example. Let’s say someone asked you to compute 2¹⁰⁰. It would take a while to manually calculate 2 x 2 x 2…etc. But if 2⁹⁹ was already given to you and stored somewhere, you would just have to do 2⁹⁹ x 2.

So with that lets try and solve a common interview question: the coin change problem.

Say we were given an amount equal to 10, with coin denominations of 1, 2, 5. (Im using a small amount and coin denominations for ease of instructions.) Hopefully the way I explain this, will be easy to follow.

How are we going to tackle this? First we are going to create an array the size of the amount + 1. Let’s call this our combinations array. Each index of the array will correlate to an amount of money. We are going to iterate through the entire array for each coin the parameters. We will start the array with a value of 0 for each index.

We start with the amount zero (0 index) with one because there is only 1 way to return the amount of 0.

Here is the code with comments on the logic:

function coinChange(amount, denominations) {
    // initialize an array of zeros with indices up to amount
    let combinations = [];
    for (let i = 0; i <= amount; i++) {
        combinations[i] = 0;
    }
    // there is only 1 way to return 0 cents
    combinations[0] = 1;for (let j = 0; j < denominations.length; j++) {
        // this will go through each of our coin denominations.
        let coin = denominations[j];//if the higher amount is less than or equal to our goal amount
        for (let higherAmount = coin; higherAmount <= amount; higherAmount++) {
            let remainder = higherAmount - coin;
            //then the remainder of the higher amount - the current coin is the index of the array
            combinations[higherAmount] += combinations[remainder];
        }
    }
    //get the last value of the array which is the total amount of combinations that can be made with the coins.
    return combinations[amount];
}let denominations = [1,2,5];
let amount = 10;
console.log(coinChange(amount, denominations));

Below is a visual representation of the flow of the function:

As you continue to increase the higherAmount variable you go through each location in the array then add the value of that index to the value of the index that the remainder reflects.

Hopefully this helped you understand the coin change problem a little more, this is the way I understood the logic and the flow.