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

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).

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

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.

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;
```

}