Minimum number of coins (DP-20)

You are given a value N and an infinite supply of some denomination of coins, you need to find out the minimum number of coins required to make the change.

Sample Input: { 1, 2, 3, 4 }, N = 15
Expected Output: 4
Explanation: {4, 4, 4, 3} can sum up to give a value of 15.

Algorithm:

This problem is a variation of the Coin Change Problem we discussed before. Instead of finding the total number of possible solutions, here we need to find the minimum number of coins.

We can use dynamic programming approach since the problem has both optimal substructure and overlapping sub-problems.

  1. We create an array DP of size (N+1) and initialize it with maximum integer.
  2. DP [i] will give the minimum number of coins required to make a change of i amount.
  3. We initialize DP [0] with 0 because a change of 0 value can be made using 0 coins.
  4. For all other values of i (1<=i<=N), we do the following.
    For all the coins in the given array, we check whether the value of the coin is greater than the current i value. If yes, we find out the solution of that subproblem stored in the DP array.
    Finally, we take the minimum of such subproblems and set the current problems solution equal to the minimum value.
#include <bits/stdc++.h>
using namespace std;

int helper(vector<int> coins, int N){
	vector<int> dp(N+1, INT_MAX);
	dp[0]=0;
	for(int i=1; i<=N; i++){
		int res = INT_MAX;
		for(int c=0; c<coins.size(); c++){
			if((i-coins[c])>=0){
				res = dp[i-coins[c]];
			}
			if(res!=INT_MAX){
				dp[i] = min(res + 1, dp[i]);
			}
		}
	}
	return dp[N];
}

int main(){
	vector<int> coins = { 1, 2, 3, 4 };
	int N = 15;
	cout<<helper(coins, N);
	return 0;
}

Also, check out another popular interview problem K-Palindromic String.

One comment

Leave a Reply

Your email address will not be published.