### 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. Comments (12)
| Write comment?
 » 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).
•  » » It doesnt work here. For example dp count 50 — 1 set and dp count 50 — 5 set, then when we counting dp we will say that dp = dp + dp + ..., so we have just counted 50 — 5 — 1 set twice. So we need to count dp[sum][max_element] to avoid such result.
•  » » » Yep, you are right. The sad thing is that I solved this problem before, what a fool I am :[
•  » » » 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 += dp, then dp += dp, etc. Then we could consider, for example, 5 cents, and the changes would be: dp += dp, dp += dp, etc. And the same for the rest of denominations.That way, each unique combination is counted once. Taking your example, dp will certainly depend on dp, dp, etc. But when dp gets added to dp, the denomination 5 has not been considered yet, so dp 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 += dp is executed. I hope this is not too confusing.Anyway, the main idea behind this process does seem to me like what sergioRG described.
 » Thanks for your response,But i still confuse with the explanation. More elaboration would be pleased.
•  » » 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.
 » dp[0..30000] — combinations to get X cents with 1-cent & 2-cent coins dp[0..30000] — combinations to get X cents with 1, 2, 5 dp[0..30000] — combinations to get X cents with 1, 2, 5, 25 dp[0..30000] — combinations to get X cents with 1, 2, 5, 25, 50 dp[X] = X / 2 + 1 dp[Y] = sum of dp[Y — 5 * k], k = 0 .. Y / 5 dp[Y] = sum of dp[Y — 25 * k] dp[Y] = sum of dp[Y — 50 * k] 
•  » » 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[X] (1- & 5- cent) would be X / 5 + 1.
 » 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.
•  » » Lookup this course on Coursera: https://www.coursera.org/course/algo2DP is explained very well there, was a good starter for me.
•  » » » Sorry, isn't there something similar but in Russian?
•  » » Try understand this first. I think this should be clear enoughhttp://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/