×

# Minimum Coin Change Problem

 0 How to solve Minimum Coin Change Problem using bottom up dp? asked 08 Feb '17, 11:46 2★rashedcs 497●5●16●54 accept rate: 4%

 1 You can refer this video. It clearly explain each and every step of this question. answered 08 Feb '17, 13:06 2.8k●1●4●18 accept rate: 16%
 1 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 4★the65bit 1.1k●10●13●28 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 community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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