Minimum Coin Change Problem

general
1

How to solve Minimum Coin Change Problem using bottom up dp?

2

You can refer this video. It clearly explain each and every step of this question.

1 Like
3

For bottom up solution, you can start filling the values from 0 and then maintaining a dp table fill the values for all the values upto n.

for (i = 1; i < n+1; i++)
{
    for (j = 0; j < m; j++)
    {
        // Count of solutions including S[j]
        x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;

        // Count of solutions excluding S[j]
        y = (j >= 1)? table[i][j-1]: 0;

        // total count
        table[i][j] = min(x,y);
    }
}

For more explanation check the GeeksForGeeks Solution. Please note Geeks For Geeks Solution is for total no of ways, for minimum coins just replace x+y with min(x,y).

1 Like
4

I want to the minimum numbers of coins to fulfill amount .

5

table[i][j] = min(x,y), will give you the minimum amount to fulfil amount i using coins upto value S[j].
So table[n][m-1] will give you minimum amount to fulfill n using coins upto S[m-1] i.e. all the coins.

1 Like
6

In this question there is a little twist in initialization part then regular question i.e. we need to fill the 2nd row of matrix as well.
Here is my code using bottom up approach.

#include<bits/stdc++.h>
using namespace std;

int coin_change(int coin[], int sum, int n){

int i,j;
int t[n+1][sum+1];

for(i=0;i<n+1;i++){
    for(j=0;j<sum+1;j++){
        if(j==0)
        t[i][j] = 0;
        else
        t[i][j] = INT_MAX-1;
    }
}
for(j=1;j<sum+1;j++){
    if(j%coin[0]==0)
    t[i][j] = j/coin[0];
    else
    t[i][j] = INT_MAX-1;
}

for(i=2;i<n+1;i++){
    for(j=1;j<sum+1;j++){
        if(coin[i-1]<=j)
        t[i][j] = min(1+t[i][j-coin[i-1]], t[i-1][j]);
        else
        t[i][j] = t[i-1][j];
    }
}
return t[n][sum];

}

int main(){
int n,i,sum;
cin>>n;
int coin[n];
for(i=0;i<n;i++){
cin>>coin[i];
}
cin>>sum;
int k=coin_change(coin, sum, n);
cout<<k<<endl;

return 0;

}

7

can anybody tell me when to use dp and when to use greedy approach in coin change problem

8

If it is asked to find the minimum number of coins to get the sum exactly equal to some integer K, we need to use DP. But if it is asked to make the sum greater than equal to some number K, we use greedy.
These are just 2 variations of the problem but it can be broken twisted in many different variations where we need to identify what to use.