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.
🧵
At the end of the thread, you will find some algorithmic challenges so you can try and apply some of the topics that I will explain today.
Feel free to skip to that part if you think you already have the necessary skills to solve them.
Let’s begin!
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).
But how can we solve this problem for any arbitrary set of coins and any amount of money?
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."
But will this algorithm work in every case?
What happens if our set of coins is c = {1, 3, 4} and the amount of money to form is 6?
The previous algorithm will select coins of values 4, 1, and 1, but the optimal answer should select 2 coins with value 3.
Most ATMs do this when you withdraw money, and it works for most global currency systems.
Ok. But, how do we solve the Coin Change problem in the general case?
The answer is Dynamic Programming!
This is a programming technique that combines the best of:
• Complete Search: should be as correct as the complete search approach to solving the same problem.
• Greedy Algorithms: 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 recursively solve the Coin Change problem, 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 our set of coins?
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.
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.
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.
But this function is still not efficient. You can notice 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.
But there are solutions to this problem!
Memoization:
Consists of enhancing our algorithm with the capacity of “remembering“ input values.
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.
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.
Problem #1: The previous algorithm returns the minimum amount of coins. How can we modify it if we want to return an example of a solution that uses a minimum amount of coins?
For example, for X = 6, and c = {1, 3, 4} we want {3, 3} as the answer.
Problem #2: What is the total number of ways in which we can produce an amount of X using a given set of coins?
For example, for X = 4, and c = {1, 3, 4} we have 4 ways:
1. 1 + 1 + 1 + 1 = 4
2. 1 + 3 = 4
3. 3 + 1 = 4
4. 4 = 4
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 👇
1. 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.
2. 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 dynamic programming.
Read the full version of this thread, including code examples and deeper explanations. Subscribe to the newsletter so you don't miss any of the weekly posts.
albexl.substack.com/p/the-coin-change-problem
And if you think this post can be helpful for someone, share it with them.
Nothing will make me happier!
See you next Monday with a new Algorithmic Problem! 👋