# minimum coin change problem

given some coins with infinite supply . Find the minimum number of coins to make the total(sum).

example:

n=3

coins={1,2,3}

sum=5

1 1 1 1 1 --- 1st

1 1 1 2 --- 2nd

1 1 3 --- 3rd

2 3 --- 4th

1 1 2 --- 5th

these are the total ways . in this the minimum is 4th ie, (2,3) which contains two coins

we will use dynamic programming to solve this question:

y is no. of test cases

n is no of different coins

a[] array to store coins

c++ implementation:

example:

n=3

coins={1,2,3}

sum=5

1 1 1 1 1 --- 1st

1 1 1 2 --- 2nd

1 1 3 --- 3rd

2 3 --- 4th

1 1 2 --- 5th

these are the total ways . in this the minimum is 4th ie, (2,3) which contains two coins

**so output=>2****if not possible print "-1".**

we will use dynamic programming to solve this question:

y is no. of test cases

n is no of different coins

a[] array to store coins

c++ implementation:

**#include <iostream>
using namespace std;
void mincoins(int a[],int n,int sum)
{
int t[n+1][sum+1];
for(int i=0;i<=n;i++)
t[i][0]=0;
for(int j=1;j<=sum;j++)
t[0][j]=10000;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=sum;j++)
{
if(a[i-1]>j)
t[i][j]=t[i-1][j];
else
t[i][j]=min(t[i][j-a[i-1]]+1,t[i-1][j]);
}
}
if(t[n][sum]==10000)
cout<<-1;
else
cout<<t[n][sum];
}
int main() {
int y; cin>>y;
while(y--)
{ int sum; cin>>sum;
int n; cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
mincoins(a,n,sum);
cout<<endl;
}
return 0;
}**