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