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.

https://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! 👋

The Coin Change Problem and Algorithmic Strategies

Ready for a healthier, happier you? 💪

7 weeks of consistent gym-going has proven to bring amazing benefits to our lives 💚.

Discover why:

🧵 👇

1/7: Increased Energy Levels

Exercise is a natural energy booster and by going to the gym 5 days a week, you'll feel a noticeable increase in your daily energy levels.

👇

2/7: Better Sleep

Regular exercise helps regulate your sleep patterns, allowing you to get better rest at night and feel refreshed the next day.

👇

3/7: Improved Mental Health

Physical activity has been shown to reduce stress, anxiety, and depression. By going to the gym, you'll be investing in your mental health too.

👇

4/7: Stronger Muscles and Bones

Strength training and weightlifting can help you build and maintain strong muscles and bones, reducing the risk of injury and age-related conditions.

👇

5/7: Better Heart Health

Regular exercise can help lower blood pressure, reduce cholesterol levels, and improve cardiovascular function, keeping your heart healthy and strong.

👇

6/7: Better Body Composition

In addition to building muscle, regular exercise can help you maintain a healthy weight and improve your overall body composition.

👇

7/7: Increased Confidence

Finally, the physical and mental benefits of regular exercise can lead to an increase in confidence and self-esteem, improving your overall quality of life.

So, there you have it! The benefits of going to the gym 5 days a week for 7 weeks straight.

Have you noticed any improvements in your life since starting a regular workout routine?

Share in the comments below!

Huge shoutout to @sheila_toledo97 for creating the game-changing weekly workout routine that has transformed me from a sedentary programmer to a fitness enthusiast 💪. Thank you! 🙌

You can read the unrolled version of this thread here: https://typefully.com/albe_xl/Z7x0h9x

7 weeks straight

Python coders, this one's for you! 🐍

Discover the must-have tool that will revolutionize the way you format your code: Black.

👇🧵

Black is a Python code formatter that ensures your code adheres to industry-standard coding guidelines.

Say goodbye to manual formatting and hello to clean, organized code! 💻

Collaborating with your team just got a whole lot easier with Black!

It helps mitigate errors by following the same formatting rules, making your projects look like "Team" code in no time 💪

Not just for Python coders, there are options for other languages too.

Imagine the boost your team will get from having consistent, organized code across projects 🚀

Ready to take your coding to the next level?

With Black, you can focus on writing great code instead of worrying about formatting.

Give it a try and see how it can change the way you code 🚀

Stay tuned for more articles at https://albexl.hashnode.dev/ and follow @albe_xl for more content in the form of threads! 🧵

You can read the unrolled version of this thread here: https://typefully.com/albe_xl/Wtn6lLx