Dynamic Programming — Number Of Ways To Make Change in 5 minutes

Understand and remember the method to solve the “Number Of Ways To Make Change” coding problem.

4 min readApr 21, 2020

The problem

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have an infinite number of each kind of coin.

You can try to solve this problem here.

Example 1:

Input:
  - Amount: 5
  - Coins: [1, 2, 5]
Output: 4
Explanation: There are 4 ways to make up the amount:
  - 5 = 5
  - 5 when= 2 + 2 + 1
  - 5 = 2 + 1 + 1 + 1
  - 5 = 1 + 1 + 1 + 1 + 1

Key point 1

What is the number of ways for the amount 0? I made a mistake in my first solution:

Wrong answer for the amount = 0$

The correct answer for the base case is 1. We can make up the amount of 0$ by not using any coins. Doing nothing is absolutely an option. And if it doesn’t sound right to you, stop and think about it.

Key point 2

Now, let’s talk about the recurrence relation. We will define the number of ways to make up the amount X, using coins [dₒ..dᵢ] as a function F. So we need to find what is the value for F(X, [dₒ..dₙ]).

Let’s use a concrete example, X = 12$ and the coins are 1$, 2$ and 5$. We’ll need to find F(12, [1, 2, 5]).

We’ll break down this example into smaller problems (subproblems).

If we have only 1$ coins:

There is only 1 way.

If we have both 1$ and 2$ coins:

Here are all the possible ways:

12$ = 12 x 1$12$ = 1 x 2$ + 10 x 1$ = 1 x 2$ + (10 x 1$) 
12$ = 2 x 2$ + 8 x 1$  = 1 x 2$ + (1 x 2$ + 8 x 1$)
12$ = 3 x 2$ + 6 x 1$  = 1 x 2$ + (2 x 2$ + 6 x 1$)
12$ = 4 x 2$ + 4 x 1$  = 1 x 2$ + (3 x 2$ + 4 x 1$)
12$ = 5 x 2$ + 2 x 1$  = 1 x 2$ + (4 x 2$ + 2 x 1$)
12$ = 6 x 2$           = 1 x 2$ + (5 x 2$ + 0 x 1$)

We have:

F(12, [1, 2]) = F(12, [1]) + F(10, [1, 2])

If we have all 1$, 2$ and 5$ coins:

Here are all the possible ways:

checking12$ = 12 x 1$12$ = 1 x 2$ + 10 x 1$ = 1 x 2$ + (10 x 1$) 
12$ = 2 x 2$ + 8 x 1$  = 1 x 2$ + (1 x 2$ + 8 x 1$)
12$ = 3 x 2$ + 6 x 1$  = 1 x 2$ + (2 x 2$ + 6 x 1$)
12$ = 4 x 2$ + 4 x 1$  = 1 x 2$ + (3 x 2$ + 4 x 1$)
12$ = 5 x 2$ + 2 x 1$  = 1 x 2$ + (4 x 2$ + 2 x 1$)
12$ = 6 x 2$           = 1 x 2$ + (5 x 2$ + 0 x 1$)12$ = 1 x 5$ + (7 x 1$)
12$ = 1 x 5$ + (3 x 2$ + 1 x 1$)
12$ = 1 x 5$ + (2 x 2$ + 3 x 1$)
12$ = 1 x 5$ + (1 x 2$ + 5 x 1$)
12$ = 1 x 5$ + (1 x 5$ + 1 x 2$)
12$ = 1 x 5$ + (1 x 5$ + 2 x 1$)

We have:

F(12, [1, 2, 5]) = F(12, [1, 2]) + F(7, [1, 2, 5])

The recurrence relation

From the above detail example, we can have the following recurrence relation:

F(X, [dₒ..dᵢ]) = F(X, [dₒ..dᵢ-₁]) + F(X - dᵢ, [dₒ..dᵢ])

Key point 3

Okay, I have to admit that I didn’t know the optimized version of this problem at the beginning. After I figured out the recurrence relation, I quickly coded it out using a 2-dimension array:

int[][] F = new int[amount + 1][coins.length];

But after looking around the Internet for others’ solutions, I found a better solution, using a 1-dimension array:

int[] F = new int[amount + 1];

Let me rewrite the above recurrence relation so that it’s more intuitive for you:

Fᵢ(X) = Fᵢ-₁(X) + Fᵢ(X - dᵢ)

This is the most important key point of this article, so make sure you grab the idea before moving on to the code below.

The solution

So, here is the code for this problem.

Solution for the number of ways to make change problem