minimum coin change problem

I will tell you the intuition behind this problem

problem statement- Consider a person want to change his money with other denominations as he needs it for his journey. He went to a shop and requests the person to change this sum. The shopkeeper is only having certain denomination’s coins with him, and he would want to give as less coins as would fit. So now we have to design an algorithm to find minimum coins which would equate to the sum

exploring greedy approach to this problem :-

suppose i am given [2,5,10,20,100,200] as coins and i need to get minimum coins to change the sum of 137.

first i will get 100 …sum now is 37 . Then i will choose coin with value 20 sum now is 17. thereafter we will choose 10 , 5, 2 coins taking the sum to 0. In this process we used 5 coins to change 137. Here greedy approach worked. But let me now take another example to counter this thought process. let us take [1,7,10] as coins and 15 . Greedily we will first take 10 then 5 of 1’s . The choice we made of taking 10 led us to use 6 coins in total. But taking two coins of 7 and 1 of 1’s also made 15 which is lesser number of coins than earlier.

Hence it is clear we cannot have optimal choice in the beginning . So we need to explore every possibility .

I chose the previous example which failed in the greedy approach. I have [1,7,10] as coins and 15 as sum. As can be seen in the picture i recursed to all the possibilities of which will equate to 15 . For getting 0 as sum we need 0 coins ,I need to know minimum coins that will change 15 , so

ans =min(f(14),f(8),f(5))+1 (+1 for current coin)

for a sum we are trying all possible coins at each step to get 0 as sum .

It has optimal substructure and overlapping subproblems (circled out subproblems are repeating ) we can store them in an array so as to reduce amount of computations . That is the idea of dynamic programming.

code recursion

int solve(int a[],int sum,int n){

if(sum==0) return 0;

int minimum=INT_MAX;

for(int i=0;i<n;i++){

if(sum-a[i]>=0) minimum=min(minimum,solve(a,sum-a[i],n));

}

return minimum+1;

}

just make a dp array initialize with zero after doing recursive code and store the result

int solve(int a[],int sum,int n,int dp[]){

if(sum==0) return dp[sum]=0;

else if(dp[sum]!=0) return dp[sum];

int minimum=INT_MAX;

for(int i=0;i<n;i++){

if(sum-a[i]>=0) minimum=min(minimum,solve(a,sum-a[i],n,dp));

}

return dp[sum]=minimum+1;

}

i talked about top down approach, you can convert this to bottom up code yourself.