Manurung's blog

How to solve this DP problem?
By Manurung, 10 years ago, In English

Anybody know the idea behind this problem?

I am a newbie in DP, help me.

This is the problem : problem

Thanks fellow.

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yep, you are right. The sad thing is that I solved this problem before, what a fool I am :[

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for your response,

But i still confuse with the explanation. More elaboration would be pleased.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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_Change

    Hope it helps.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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]
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply