You are not logged in. Please login at to post your questions!


Minimum Coin Change Problem

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

asked 08 Feb '17, 11:46

rashedcs's gravatar image

accept rate: 4%

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


answered 08 Feb '17, 13:06

bansal1232's gravatar image

accept rate: 16%

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


answered 08 Feb '17, 22:29

the65bit's gravatar image

accept rate: 13%

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

(09 Feb '17, 10:08) rashedcs2★

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.

(09 Feb '17, 10:35) the65bit4★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 08 Feb '17, 11:46

question was seen: 1,888 times

last updated: 09 Feb '17, 10:35