Hem's Blog: Data Structures and Algorithms - Problem

In this blog, We are going to solve another Dynamic Programming problem using Brute Force and Memoization.

Problem Statement:- You have an integer array of coins of different denominations and an integer amount representing an amount of money. You have an infinite number of each coin, and the order of coins doesn't matter.

What we need to return is the fewest number of coins that we need to make up that amount.

 Example 1: coins [10,20,50] and the amount is 100  
 Option 1 :- 10 x 10 = 100  
 Option 2 :- 20 x 5 = 100  
 Option 3 :- 50 x 2 = 100  
 Option 4 :- 10 x 8 + 20 x 1 = 100

As we can see we computed four options by which we can get to 100 using available coins but what we need is the fewest, and in that case, Option 3 is our best option. Now let's understand how we can solve this using Dynamic Programming.

Let's see another example

 Example 2: coins [10,30,40,50] and the amount is 70  
 Option 1 :- 10 x 7 = 70   
 Option 2 :- 50 x 1 + 10 x 2 = 70  
 Option 3 :- 40 x 1 + 30 x 1 = 70

In example 2 the fewest coins we would require is 2 as per option 3.

Can we solve this problem using a Greedy algorithm? Which always starts with the biggest number that's why "GREEDY".

In Example 2, Option 2 is the example of being Greedy, Where we started with the biggest number but that took us 3 coins value to get the final result, and option 3 took 2 coins value to get the result, Which means the GREEDY algorithm is not we want to use here.

What other approach, we can use here, Dynamic Programming and Brute Force? let's try that. In order to use Bruteforce, We need to implement DFS (Depth First Search).

What we are doing here is we are subtracting the coins {10,30,40,50} from 70 which is our total amount, and we will continue subtracting coins till we reach 0 or stop doing it if the output is negative.

Let's see the code, and understand how we can solve this problem. In the below code, we followed example 2 and the output is as expected.

We should try one more example and this time the coins[] = {1,2,3} and amount = 7. The fewest coins combination would be 3 x 2 + 1 x 1 = 7, which means a total of 3 coins.