In this guide, we will explore one of the frequently encountered interview questions. The coin change conundrum serves as an excellent illustration of employing a dynamic programming strategy. Let's delve into comprehending the issue at hand.
Problem statement
Given an integer N and an array called coins, which holds different denominations of coins, where N represents a specific coin value and the array consists of various coin denominations. The objective is to provide change for N using the coins from the array in a manner that minimizes the number of coins utilized.
Example
Let's consider an input array coins = {10, 25, 5}, where the total number of coins is 3.
We have N = 30.
The result is two since we can combine a 25 rupee coin with a 5 rupee coin to total 30. (25 + 5 = 30)
Likewise, coins = {1, 9, 6, 5}, total number of coins = 4
N = 13
The result is three because it requires two 6 rupees coins and one 1 rupee coin. (6 + 6 + 1 = 13)
Approach 1
The method involves employing a recursive strategy. It commences with the value N, and at each step, it breaks down the issue into more manageable sub-problems. This is achieved by selecting each coin from the array of coins and subtracting it from N. When N reaches zero, the desired solution is obtained. To obtain the most efficient outcome, the function returns the smallest value among all possible combinations.
C++ code
#include <bits/stdc++.h>
using namespace std;
int minCoins(int coins[], int total_coins, int N) // Function to return the minimum // coins needed
{
if (N == 0) // If we have a combination then
return 0;
int result = INT_MAX; // Currently result is initialised as INT_MAX
for (int i = 0; i < total_coins; i++) // run until availability of coins
{
if (coins[i] <= N) { // Add to the list of counting
int sub_res = 1 + minCoins(coins, total_coins, N - coins[i]); // add 1 due to the coin inclusion
// see if result can minimize
if (sub_res < result)
result = sub_res;
}
}
return result;
}
int main()
{
int coins[] = { 10, 25, 5 };
int sum = 30; // the money to convert
int total_coins = 3; // total availability of coins
cout << "Minmum coins needed are " << minCoins(coins, total_coins, sum);
}
Output
Minimum coins needed are 2
The previous solution is inadequate for handling larger inputs. In such scenarios, the recursive method proves to be ineffective.
Now let us look at an optimized approach.
Approach 2
This method employs the concept of bottom-up dynamic programming.
As subtasks are recalculated repeatedly, a scenario of overlapping subproblems arises. The issue of redundant calculations can be addressed by employing the concept of memoization. This involves establishing a dp array to retain the calculated values at a specific point. Progressively evaluate all feasible permutations at each juncture. Upon considering all permutations, the final value in the dp array furnishes the solution.
C++ code
#include <bits/stdc++.h>
using namespace std;
int coins[] = { 10, 25, 5 }; // coins array
int dp[1000] = { 0 }; // array for memoisation
int minCoins(int N, int M) // N is the sum , M is total_coins
{
for (int i = 0; i <= N; i++)
dp[i] = INT_MAX; // Initialise all dp[] value to INT_MAX
dp[0] = 0; // Base case if sum becomes zero min rupees = 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()
{
int sum = 30; // the money to convert
int total_coins = 3; // total availability of coins
cout << "Minimum coins needed are " << minCoins(sum, total_coins);
}
Output
Minimum coins needed are 2
The computational complexity of the algorithm is O(total_coins + sum). This strategy is highly efficient due to saving the outcomes at each step and leveraging them in subsequent iterations.
