### Manurung's blog

By Manurung, 9 years ago,

Anybody know the idea behind this problem?

I am a newbie in DP, help me.

This is the problem : problem

Thanks fellow.

• -2

| Write comment?
 » 9 years ago, # |   0 Main idea:If you know there are k ways to get c cents, then also you have found k ways to get c + m cents, where m is any valid coin value (1,5,10,25 and 50 for this problem).
•  » » 9 years ago, # ^ |   +1 It doesnt work here. For example dp[51] count 50 — 1 set and dp[55] count 50 — 5 set, then when we counting dp[56] we will say that dp[56] = dp[55] + dp[51] + ..., so we have just counted 50 — 5 — 1 set twice. So we need to count dp[sum][max_element] to avoid such result.
•  » » » 9 years ago, # ^ |   0 Yep, you are right. The sad thing is that I solved this problem before, what a fool I am :[
•  » » » 9 years ago, # ^ |   0 An interesting point, although I've just checked my solution to this problem and my DP variable was simply: i64 dp[MAXN+1]; // dp[m]: the number of ways to produce m money One thing to consider is that in order for this to work the dp states have to be calculated in order, each denomination at a time. For example, if we start by considering 1 cent, then dp[1] += dp[0], then dp[2] += dp[1], etc. Then we could consider, for example, 5 cents, and the changes would be: dp[5] += dp[0], dp[6] += dp[1], etc. And the same for the rest of denominations.That way, each unique combination is counted once. Taking your example, dp[56] will certainly depend on dp[55], dp[51], etc. But when dp[55] gets added to dp[56], the denomination 5 has not been considered yet, so dp[55] is not counting [50 — 5] (given the order chosen above, but selecting the denominations in any order works). [50 — 5 — 1] will only be counted later, when dp[56] += dp[51] is executed. I hope this is not too confusing.Anyway, the main idea behind this process does seem to me like what sergioRG described.
 » 9 years ago, # |   0 Thanks for your response,But i still confuse with the explanation. More elaboration would be pleased.
•  » » 9 years ago, # ^ |   +1 Let me Count the Ways (UVa 357) is an instance of a classic problem known as "coin change", with a well-known DP solution. I'd recommend investing a little time searching the web about it, because that way you may find a few references written in a style that "clicks" with you.As a starting point, a good introduction is, for example: http://www.algorithmist.com/index.php/Coin_ChangeHope it helps.
 » 9 years ago, # |   0 dp[0][0..30000] — combinations to get X cents with 1-cent & 2-cent coins dp[1][0..30000] — combinations to get X cents with 1, 2, 5 dp[2][0..30000] — combinations to get X cents with 1, 2, 5, 25 dp[3][0..30000] — combinations to get X cents with 1, 2, 5, 25, 50 dp[0][X] = X / 2 + 1 dp[1][Y] = sum of dp[0][Y — 5 * k], k = 0 .. Y / 5 dp[2][Y] = sum of dp[1][Y — 25 * k] dp[3][Y] = sum of dp[2][Y — 50 * k] 
•  » » 9 years ago, # ^ |   0 My bad There are [1,5,10,25,50] coins in the problem, my solution is for [1,2,5,25,50]. But the idea remains the same, dp[0][X] (1- & 5- cent) would be X / 5 + 1.
 » 9 years ago, # |   0 Thanks for the great elaboration.Actually I'm still confuse, maybe it's too fast to me to learn DP. I will get some sources, and do some self-study on it.
•  » » 9 years ago, # ^ |   +3 Lookup this course on Coursera: https://www.coursera.org/course/algo2DP is explained very well there, was a good starter for me.
•  » » » 9 years ago, # ^ |   0 Sorry, isn't there something similar but in Russian?
•  » » 9 years ago, # ^ |   +3 Try understand this first. I think this should be clear enoughhttp://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/