Dynamic Programing using Tabulation and bottom-up approach solution to solve Coin Change Challenge.

In this post, we are going to use Dynamic programming to solve coin change problem,

Dynamic programming is an algorithmic technique for solving the optimizing problem by breaking it down into simpler subproblems.

Problem

we have an array of integers of coins {c1,c2,c3,c4,c5,}and the total value of change that we are going to make, so in this problem, we are going to check how many ways we can make to get the Total change that given us in the input.

We are going to make tabulation in,

Tabulating is a way of processing information or data by putting it in a table. Our table includes coins as a row and Total as a column, starting by filling the first row of the table, before starting to write our program we are going to compute each value in our first row. We are splitting our total to many totals starts in sequence. n,n+1,n+2…t , 0,1 ….10

Our test case includes coins =[2,5,3,6] and the total is 10, so how many ways we can 10 form provided coins.

If coin 2, total = 0  1 result 1 because we can make 0 change in any number.

If coin 2, total = 1  0 results 0 because we can’t make 2 changes from 1.

If coin 2, total = 2  1 result 1 because we can make 2 change from 2.

If coin 2, total = 3  0 results 0 because we can’t make 3 change from 2, it will remain 1 If coin 2, total = 4  1 result 1 because we can make 2 change from 2.

Also, we will fill all first column by 1 because all coins can make 0 change

No, we are going to write part of a program by using for loop and our 2D array to fill up the tabulation above.

Our two-dimension array row size will be coin size, and the column size will be total+1 size because it will start from 0

Long A[][] =new Long[coin.size()][n+1];

for(int m=1;m<n+1;m++) {

if(m < coin.size()) {

A[m-1][0]= 1L;

}

if(coin.get(0) > m ) {

A[0][m]= 0L;

}else {

A[0][m] =A[0][(int) (m-coin.get(0))];

}

}

In the next step we ae going to fill up our table by using this technique

A[i][j] = A[i-1][j];

Or

A[i][j]=A[i-1][j]+A[i][(int)(j-coin.get(i))];

If coin 5, total = 1  0 results 0 because we just copy the previous row in the same column which is 0.

If coin 5, total = 2  1 result 1 because we just copy previous row same in the same column which is 1 .

If coin 5 , total = 3  0 results 1 because we just copy the previous row in the same column which is 0 .

If coin 5, total = 6  1 result 1 because we copy the previous row in the same column which is 0 and we add the value of the previous field of current column(coins)- current row(totals)

Which is 1, so 0+1 =1

If coin 5, total = 10  2 results 2 because we copy the previous row in the same column which is 1 and we adding the value of the previous field of the current column(coins)- current row(totals) which is also 1, so 1+1 =2.

Thus this process will continue until the end of the loop, at the end, the last field of columns and last row will be the total ways, so in this example, it will be something like this

If coin 6, total = 10  5 results 5 because we copy the previous row in the same column which is 4 and we adding the value of the previous field of current column(coins)- current row(totals) which is also 1, so 4+1 =5.

The reason we are adding previous row + (current column — current row),

because we are adding previous of all coin + current coin.

for(int i = 1;i<= coin.size()-1;i++){

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

if(coin.get(i) > j){

A[i][j] = A[i-1][j];

}

else{

A[i][j] = A[i-1][j] + A[i][(int) (j- coin.get(i))];

}

}

}

return A[coin.size()-1][n];