**Difficulty:** Medium, **Asked-in:** Microsoft, Amazon, Morgan Stanley

**Key takeaway:** An excellent optimization problem to learn problem-solving using dynamic programming.

We are given amount **K** representing total amount of money and integer array coin[] of size m representing coins of different denominations. Write a program to find the minimum number of coins required to make change.

We may assume that we have an infinite supply of each kind of coin with the value coin[0] to coin[m-1]. If any combination of the coins cannot make up amount K of money, we return -1.

**Example 1**

Input: coin[] = [25, 10, 5], K = 30, Output: 2

Explanation: Minimum 2 coins required: we can use one coin of 25 and one coin of 5.

**Example 2**

Input: coin[] = [9, 6, 5, 1], K = 13, Output: 3

Explanation: Minimum 3 coins required: we can use two coins of 6 and one coin of 1.

**Example 3**

Input: coin[] = [1, 3, 5, 7], K = 18, Output: 4

Explanation: Minimum 4 coins required. We can use any one of these combinations to provide change using 4 coins: (7, 7, 3, 1),(5, 5, 5, 3), and (7, 5, 5, 1).

- A brute force approach using recursion
- An efficient approach using bottom-up approach of DP

This is an optimization problem because there can be several ways to provide change, but we need to return the change using the minimum number of coins. In different words : Solution space is huge and only a few solutions will provide the optimal solution. So one basic idea would be to explore all solutions or possibilities of the change and return the count of with a minimum number of coins. The critical question is : How do we implement this? Let’s think!

- In such a situation, when we need to explore all possibilities, we can think about solving the problem recursively, i.e. the solution of problem using smaller sub-problems.
- Initially available choices are important for building recursive solution. Here we have m choices of coin in the start i.e. we can pick any coin among m coins.
- Suppose
**minCoin(coin[], m, K)**returns the minimum number of coins required to make change of value K (This is our larger problem). If we select any coin[i] first, the smaller sub-problem is**minCoin(coin[], m, K - coin[i])**i.e. the minimum number of coins required to make a change of amount K - coin[i]. - So, for i = 0 to m - 1, whichever choice provides the change using minimum number of coins, we shall add 1 and return the value. Before selecting any coin, make sure whether the value of the coin is less than equal to the amount needed i.e.
**coin[i] <= K.** -
Recursive structure:

minCoin(coin[], m, K) = min (for i = 0 to m - 1) { 1 + minCoin(coin[], m, K - coin[i]) }

Where coin[i] <= K

- Base case: If K == 0, then 0 coins required.

```
int minCoin(int coin[], int m, int K)
{
if(K == 0)
return 0
int minCount = INT_MAX
for(int i = 0; i < m; i = i + 1)
{
if(coin[i] <= K)
{
int currCount = minCoin(coin, m, K - coin[i])
if(currCount != INT_MAX && currCount + 1 < minCount)
minCount = currCount + 1
}
}
if(minCount == INT_MAX)
return -1
else
return minCount
}
```

From the above observation, if we increase value of K or value of m, the total number of recursive calls will increase. So time complexity depends on both K and m i.e. Input size = (K, m).

For the upper bound of worst-case analysis, suppose coin[i] <= K during each recursive call and, the recursion tree would be a full tree where each child has m nodes. So we have m number of recursive calls at the 1st level of the recursion tree, m^2 number of recursive calls at the 2nd level of the recursion tree, and so on.

Total number of recursive calls in the worst-case = 1 + m + m^2 + ... m^k = (m^k - 1) / (m -1) = O(m^k), which is an exponential time. **Note:** Sum of the geometric progression S = a + ar + ar^2 +...+ ar^n = a(r^n - 1)/(r - 1), where r > 1.

In retrospect, this is not surprising because we are exploring all possibilities to provide change. If we create a recursion tree for above approach, then clearly notice overlapping or repeated subproblems.

For example, following picture is the recursion tree diagram for K = 5 and coins of given values [1, 2, 3]. The sub-problem of size 3 is coming 2 times, sub-problem of size 2 is coming 4 times, sub-problem of size 1 is coming 7 times.

Since we have identified that it is a dynamic programming problem, we can solve it using the bottom-up approach. Our aim here is to calculate solution of smaller problems in an iterative way and store their result in a table. The critical question is : How do we build the solution in a bottom-up manner? Let’s think!

**Table structure:**The state of the smaller sub-problems depends on the one variable**K**because it decreases after each recursive call. So we need to construct a 1-D table to store the solution of the sub-problems.**Table size:**The size of the 1-D table is equal to the total different subproblems. According to the recursion tree, there can be a total (K + 1) of different sub-problems i.e sub-problems of size (K, K-1,…2, 1, 0).**int Change[K + 1]****Table initialization:**Before building the solution using iterative structure of bottom-up approach, we need to initialize table by the smaller version of solution i.e base case.**Change[0] = 0**-
**Iterative structure to fill the table:**Now, we need to define iterative structure to fill the table Change[i] i.e a relation by which we build solution of larger problem using solution of smaller problems in a bottom-up manner. We can easily define iterative structure by using recursive structure of the recursive solution.Change[i] = min (for j = 0 to m-1) { 1 + Change[i - coin[j]] }, where coin[j] <= K

**5. Returning the final solution:** After filling the table iteratively, our final solution gets stored at the last Index of the array i.e.return **Change[K].**

```
int minCoin(int coin[], int m, int K)
{
if(K == 0)
return 0
int Change[K + 1]
Change[0] = 0
for(int i = 1; i <= K; i = i + 1)
Change[i] = INT_MAX
for(int i = 1; i <= K; i = i + 1)
{
for(int j = 0; j < m; j = j +1)
{
if(coin[j] <= i)
{
int currCount = Change[i - coin[j]]
if(currCount != INT_MAX && currCount + 1 < Change[i])
Change[i] = currCount + 1
}
}
}
if(Change[K] == INT_MAX)
return -1
else
return Change[K]
}
```

There are two nested loops in the code. The first loop is iterating from 1 to K and the second is iterating from 0 to m-1. Time complexity = O(K*m). Space complexity = O(K), for extra array Change[] of size K + 1.

- Do we require the entire array of size equal to K or can we optimize the space? Think about the case when the amount is too high.
- How can we modify the code to find the coins which are part of the optimal solution?
- Can we solve this problem using some other approach? Can we think of applying the greedy or divide and conquer strategy?
- Explore DP problems that can be solved using a similar idea.
- Why is the recursive solution exponential time? Try to analyze the recursive code using the recursion tree method.
- Think about the top-down approach to solve this problem

- Find the number of ways in which you can change an amount with given coins of different denominations.
- Greedy algorithm to find minimum coin count.
- Rod cutting problem
- 0–1 Knapsack problem
- Weighted job scheduling

**Enjoy learning, Enjoy algorithms!**

Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.