Algorithmically Speaking - #1: Coin Change
Let's unravel the Coin Change problem together.
This is the summary version of the article published in the Algorithmically Speaking newsletter which is only dedicated to exploring some of the most beautiful algorithmic problems and solutions in the history of Computer Science.
You can read the complete version by clicking on this link.
Hello there!
Today we are going to be diving into one of the most common algorithmic problems we face in our daily lives: the Coin Change problem.
This problem is the perfect excuse for me to introduce you to Greedy Algorithms and Dynamic Programming.
Let’s begin!
Formulating the Problem
In its simplest terms, the problem can be formulated as follows:
We are given a set of coins and our task is to form a sum of money N using the coins. The values of the coins are c = {c1, c2,..., ck}, and each coin can be used as many times as we want. What is the minimum number of coins needed?
As an example, let’s say our set of coins is c = {1, 3, 4}, and we want to form an amount of money equal to 5. In this case, it is optimal to select 2 coins (one with a value of 1 and another with a value of 4).
Trust me on this, we cannot create that amount of money with this set of coins using less than 2 coins. But how can we solve this problem for any arbitrary set of coins and any amount of money?
Greedy Solution
A very intuitive and easy solution that might come to everyone’s mind is the following:
Always select the largest possible coin, until the required sum of money has been reached.
Let’s face it. We would probably do this if we have to solve this problem in real life. This algorithm works in our example case above, let’s see how:
We start with an amount of money equal to
0.We select a coin with value
4. We have an amount of money equal to4.We select a coin with the value
1. We have an amount of money equal to5. We finish our algorithm.
But will this algorithm work in every case?
First, this is a Greedy algorithm. These algorithms construct solutions by always making the choice that seems like the best at the moment. You never take back any choice if you use a greedy algorithm. Instead, you directly construct the solution. This is why greedy algorithms are usually very efficient.
Nevertheless, the fact that greedy algorithms always select optimal local choices makes it difficult to prove their correctness. To do it properly, you should be able to argue that all the optimal local choices are also globally optimal.
Luckily for us, despite the difficulty to prove the correctness of a greedy algorithm, showing they are not always correct is a lot more simple: we just have to find an example case where it produces the wrong output.
For example, what happens with this algorithm if we take the same set of coins as above but now we want to form an amount of money equal to 6?
First, it will select a coin with value 4, then a coin with value 1, and then another one with value 1. This indeed adds up to the amount we want, and it uses 3 coins. Nevertheless, if we choose two coins with value 3, we end up with a solution that uses fewer coins than the greedy algorithm proposed.
We have shown that this algorithm doesn’t produce the optimal result in every case!
Despite that, this algorithm is really good. And it does work for any amount of money if we have the appropriate set of coins. Most ATMs do this when you withdraw money, and it works for most global currency systems.
Now, instead of diving into when this greedy algorithm works, let’s focus on a more interesting question: how do we solve the Coin Change problem in the general case?
Dynamic Programming Solution
Dynamic Programming can be seen as a programming technique that combines the best of two other techniques:
Complete Search: A dynamic programming solution should be as correct as the complete search approach to solving the same problem.
Greedy Algorithms: A dynamic programming solution should be as efficient as greedy algorithms usually are.
This technique can be applied when the problem can be divided into overlapping subproblems that can be solved independently. Usually, the relation between the solution for a problem and the solution for the subproblems that it will be divided is represented by a recurrence.
If we were to solve the Coin Change problem recursively, we could define a function f(x) that will answer the following question: what is the minimum amount of coins needed to form an amount of x, with the set of coins that we have?
For example, assuming our coins are c = {1, 3, 4}, the answer for the first few cases is:
f(0) = 0
f(1) = 1
f(2) = 2
f(3) = 1
f(4) = 1
f(5) = 2
The good thing that the function f has is that its value can be calculated by recursively evaluating the function in smaller input values. And the key idea to formulate the recursive solution is to focus on the first coin we choose every time.
Let’s say we are calculating the answer for x = 9. In this case, we know that the first coin we choose has to be one of 1, 3, or 4 because those are the only coins we have available. In case we decide to go for a coin with the value of 1, then we will face the problem of forming the amount of 8 using the minimum amount of coins. This is the same original problem we are trying to solve, but now in a smaller instance. Hence, a subproblem. The same goes for coins with values 3 and 4.
Generalizing, our recursive formula to solve the Coin Change problem with this set of coins is as follows:
f(x) = min(f(x - 1) + 1,
f(x - 3) + 1,
f(x - 4) + 1)
The base case for our recursion is when x = 0. In that case, the answer is 0 because we don’t need any coins to form an empty amount of money. And, just to make the implementation easier, let’s say that the answer for x < 0 is an infinitely large number because there is no answer for a negative amount of money.
That being said, we could implement the described algorithm like this:
def f(x):
if x < 0:
return INF
if x == 0:
return 0
ans = INF
for value in coins:
ans = min(ans, f(x - value) + 1)
return ans
But this function is still not efficient. If you are sharp enough, you might have noticed that this function calculates the value for the same input several times. For example, two possible recursion paths are the following when solving f(9):
f(9) --> f(6) --> f(2)
f(9) --> f(5) --> f(2)
In both of these paths, we go through solving for x = 2, which is a waste of time and resources. If we had a way of recording the input values for which we already know the solution, the performance of our recursive algorithm will improve.
Fortunately, we can achieve this behavior using one of the following methods:
Memoization
Memoization consists of enhancing our algorithm with the capacity of “remembering“ the input values that have already been solved. That way, whenever our algorithm notices that a value has been processed already, it can return the value that was calculated for that input the first time it was seen.
The easiest way of adding memoization to your algorithm is probably to create a structure that can map an input value to a boolean value, to store which inputs have been seen already. On top of that, we can do the same with a structure that maps input values to the outputs that our recursive function returns for those inputs.
In our case, we could modify our previous recursive function to something like this:
def f(x):
if x < 0:
return INF
if x == 0:
return 0
if seen[x]:
return value[x]
ans = INF
for coin in coins:
ans = min(ans, f(x - coin) + 1)
seen[x] = True
value[x] = ans
return ans
Iterative Solution
The second way to improve the performance of our recursive algorithm is to not implement it using recursion at all!
Almost always, it is possible to find ways to implement recursive solutions using an iterative approach. This way is often harder to come up with, and recursive thinking might be the preferred way to go when trying to come up with solutions to similar problems. But still, I think it is good to know and usually, it is a good exercise to try to translate a recursive algorithm to an iterative implementation.
In our case, we need to solve our subproblems in an order that guarantees that when we are solving f(x), all the subproblems derived from x are already solved. That order is {0, 1, …, x}.
Let’s see a sample implementation:
def f(x):
value[0] = 0
for i in range(1, x + 1):
value[i] = INF
for coin in coins:
if i - coins >= 0:
value[i] = min(value[i], value[i - coin] + 1)
return value[x]
This iterative approach is often known as a Bottom-Up approach, while the recursive one with memoization is referred to as a Top-Down approach.
Conclusions
I hope I was able to ignite your passion for Greedy algorithms and Dynamic programming by driving you through one of the most classic algorithmic problems in the history of Computer Science.
Some takeaways:
I think it’s worth noticing how we were able to start with a greedy algorithm that doesn’t always produce the correct output and end up with an efficient dynamic programming solution.
Greedy algorithms are great, even if they don’t always work. Sometimes they are good enough, and the performance advantage they provide is often a good thing to consider in real-life problems.
Problems that can be broken down into subproblems often can be formulated with a recurrence formula. This formula translates to a recursive algorithm almost naturally. This recursion can be optimized by “caching“ the input using memoization. That is the basis of dynamic programming.
I wish you good luck when solving this week’s challenges. Don’t forget to share your progress with the community!
And if you think this post can be helpful for someone, share it with them. Nothing will make me happier!
See you next week!
👋 Hello, I'm Alberto, Software Developer at doWhile, Competitive Programmer, Teacher, and Fitness Enthusiast.
🧡 If you liked this article, consider sharing it.