Trusted answers to developer questions

Harsh Jain

In this article, I will solve a famous problem using the dynamic programming (DP) approach. The name of the problem is **minimum coin change** and it is very popular in interviews.
The problem statement is:

If we want to make change for a given value (N) of cents, and we have an infinite supply of each of C = { $C_{1}$, $C_{2}$, … , $C_{M}$} valued coins, what is the minimum number of coins required to make the change?

```
Example ->
Input:
coins[] = {25, 10, 5}, N = 30
Output: Minimum 2 coins required
We can use one coin of 25 cents and one of 5 cents.
Input:
coins[] = {9, 6, 5, 1}, N = 13
Output: Minimum 3 coins required
We can use one coin of 6 + 6 + 1 cents coins.
```

Before moving on to the solution, I would like you to try this on your own first.

Start the solution with $sum = N$ cents and, in each iteration, find the minimum coins required by dividing the problem into sub-problems where we take a coin from {$C_{1}$, $C_{2}$, …, $C_{M}$} and decrease the sum, $N$, by $C[i]$ (depending on the coin we took). Whenever $N$ becomes 0, this means we have a possible solution. To find the optimal answer, we return the minimum of all answers for which $N$ became 0.

If `N == 0`

, then 0 coins are required.

If `N > 0`

then,

```
minCoins(N , coins[0..m-1]) = min {1 + minCoins(N-coin[i], coins[0....m-1])}
```

where `i`

varies from `0`

to `m-1`

and `coin[i] <= N`

.

#include<bits/stdc++.h> using namespace std; // Recursive Function int minCoins(int coins[], int m, int N) { // base case if (N == 0) return 0; // Initialize result int res = INT_MAX; // Try every coin that has smaller value than m for (int i=0; i<m; i++) { if (coins[i] <= N) { int sub_res = 1 + minCoins(coins, m, N-coins[i]); // see if result can minimized if (sub_res < res) res = sub_res; } } return res; } int main() { int coins[] = {1,2,3,4,5}; int sum = 11; int total_coins = 5; cout << minCoins(coins,total_coins,sum); }

Recursive solution to the problem

It is easy to see that recursive solutions can require high computations.

You can check this by changing the `sum`

variable’s value to a high value to see an execution time error, which means that our solution is not optimized. This is where most candidates fail in their interviews.

Let’s try dynamic programming now!!

Since the same subproblems are computed again and again, this problem has the *overlapping subproblems* property.

Like other typical dynamic programming problems, re-computations of the same subproblems can be
avoided by constructing a temporary array `dp[]`

and memoizing the computed values in that array.

#include <bits/stdc++.h> using namespace std; int coins[] = {1,2,3,4,5}; int dp [1000] = {0}; int minCoins(int N, int M) { //Initializing all values to INT_MAX i.e. minimum coins to make any //amount of sum is INT_MAX for(int i = 0;i<=N;i++) dp[i] = INT_MAX; //Base case //Minimum coins to make sum = 0 cents is 0 dp[0] = 0; //Iterating in the outer loop for possible values of sum between 1 to N //Since our final solution for sum = N might depend upon any of these values for(int i = 1;i<=N;i++) { //Inner loop denotes the index of coin array. //For each value of sum, to obtain the optimal solution. for(int j = 0;j<M;j++) { //i —> sum //j —> next coin index //If we can include this coin in our solution if(coins[j] <= i) { //Solution might include the newly included coin dp[i] = min(dp[i], 1 + dp[i - coins[j]]); } } } return dp[N]; } int main() { // your code goes here int sum = 50; int total_coins = 5; cout << minCoins(sum, total_coins); }

Dynamic programming solution to the problem

So, that’s the dynamic programming approach. We used memoization, saved the solution of the subproblems, and then returned the optimal solution.

The complexity is $O(M*N)$ in this solution, where $M$ is the number of coins and $N$ is the change required. You can see that, because of memoization, we get the output pretty fast, even with a higher value of `sum`

.

As an exercise, try to implement one more solution that uses recursion and dynamic programming. It is usually called the **top-down dynamic programming approach**. The approach we discussed here is **bottom-up**.

Thanks for reading!!

RELATED TAGS

interview

c++

communitycreator

CONTRIBUTOR

Harsh Jain

RELATED COURSES

View all Courses

Keep Exploring

Related Courses