Anybody know the idea behind this problem?

I am a newbie in DP, help me.

This is the problem : problem

Thanks fellow.

# | User | Rating |
---|---|---|

1 | Benq | 3783 |

2 | jiangly | 3666 |

3 | tourist | 3611 |

4 | Um_nik | 3536 |

5 | inaFSTream | 3477 |

6 | fantasy | 3468 |

7 | maroonrk | 3464 |

8 | QAQAutoMaton | 3428 |

9 | ecnerwala | 3427 |

10 | Ormlis | 3396 |

# | User | Contrib. |
---|---|---|

1 | Um_nik | 185 |

2 | adamant | 178 |

3 | awoo | 177 |

4 | nor | 169 |

5 | maroonrk | 165 |

6 | -is-this-fft- | 164 |

7 | antontrygubO_o | 153 |

8 | ko_osaga | 151 |

9 | dario2994 | 150 |

10 | SecondThread | 149 |

Anybody know the idea behind this problem?

I am a newbie in DP, help me.

This is the problem : problem

Thanks fellow.

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/02/2023 01:05:41 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Main idea:

If you know there are

kways to getccents, then also you have foundkways to getc+mcents, wheremis any valid coin value (1,5,10,25 and 50 for this problem).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.

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:

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.

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_Change

Hope it helps.

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

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 beX / 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/algo2

DP 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 enough

http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/