You are not logged in. Please login at www.codechef.com 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

2★rashedcs
49751654
accept rate: 4%


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

link

answered 08 Feb '17, 13:06

bansal1232's gravatar image

5★bansal1232
2.8k1418
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).

link

answered 08 Feb '17, 22:29

the65bit's gravatar image

4★the65bit
1.1k101328
accept rate: 13%

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

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

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
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×2,086

question asked: 08 Feb '17, 11:46

question was seen: 1,888 times

last updated: 09 Feb '17, 10:35