Number of Ways To Make Change

Dynamic Programming

We are essentially going to create an array with the size of the target number. This array will keep track of the number of ways we can use the coins in order to generate the amount at that particular index in the array.

For example, Consider target = 10.

So, we create an array of size 10+1, and fill it with 0s.

ways = [0,0,0,0,0,0,0,0,0,0,0];

Now, every index in the array, will represent the target sun. Therefore, arr[5] value will depict the number of ways to generate a target amount of 5 using the denominations.

Also, ways[0] will ALWAYS be 1 because there's essentially only 1 way to generate target of 0, which is using no coins at all.

The formula that is used is:

if (denom <= amount) {
    ways[amount] += ways[amount - denom]
}

So for example, ways[5] = ways[5] + ways[5 - 1] will be the formula IF we are traversing the 1 denomination value.

• Iterate the denominations array
• Iterate the ways array.
• Check if denom <= amount. If Yes, use ways[amount] += ways[amount - denom] to update the array.
• Return the last value in the ways array, because ways[target] is what we are interested in. And the last value will always be the target value in our case.

Time and Space Complexity

• O(nd): Time where d is the number of denominations and n is the target value.
• O(n): space where n is the target value.