| # | User | Rating |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 165 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | SecondThread | 145 |
| 9 | pajenegod | 145 |
I got stuck with this problem for quite a time now.It can be counted how many ways to make N with a number of coins.But I have no idea how to answer range query for this problem.
Any detailed hint of overall solution of this problem,it will be so much helpful.Thanks in advance.
First, calcualte the DP. Let DPi, j be the way to pay i dollars using exactly j coins. Calculate the DP the normal way (judging from your post, I assume you already know how to do that), and then sum the previous values. That is, for all [i, j], set DPi, j = DPi, j + DPi, j - 1. So now DPi, j means the way to pay i dollars using at most j coins.
Another thing to notice is that there's no way to pay a price ≤ 300 with more than 300 coins. Now, to answer the queries...
Would you please elaborate why for the third type : DP [n,l2] — DP[n,l1-1] would work ?
Normally I would try to do it with a for loop,but constraints are large.Why this thing would work like range sum ?
Just think about it, if you do (1 + 2 + 3 + 4 + 5 + 6 + 7) - (1 + 2 + 3 + 4), you get (5 + 6 + 7). This is the same idea.
tenshi_kanade I thought the same . but there is something more to this question . quote from the question " For example, by using three coins one can pay six dollars in 3 ways, 1+1+4, 1+2+3, and 2+2+2" but if we do by conventional method this would have 1+1+4 and 4+1+1 as 2 different ways of paying as simply answer would have been n+k-1 C k-1 ( x1+x2+x3...xk=n and x1,x2,x3..xk>=1) which results into different answer
To overcome that issue, you can iterate by coin value, then by price, then by amount of coins. If you do it that way, you can make sure that first you count all ways that use up to coin with value v, then all ways that use coins with value up to v + 1, etc..
I can share the source code if I'm not clear enough...
sharing code will do.
OK, here it is: C++ Code
As you can see, to make sure we don't count one way many times, we first iterate by coin value c, then by price i, then by amount of coins j.
Perhaps if I had used a 3D array DPc, i, j that stores the ways to pay i dollars by using exactly j coins with values ≤ c, , it might be clearer and easier to understand. In tbat case, the transition would be DPc, i, j = DPc - 1, i, j + DPc, i - c, j - 1.
But it's not necessary to use O(N3) memory, so I just coded the shortest and more efficient form using O(N2) memory.
Then, your above recurrence relation is incorrect.
Correct one: DPi, j, k = DPi - k, j - 1, k + DPi, j, k - 1
that is the number of ways of getting i dollars using j of first k type coins. DP array is 2-dimensional because of memory optimization.
What is incorrect? I don't know what you mean.
The way you describe here is what I explained above, but it's not necessary to use O(N3) memory. I know you can get away with O(N2) memory even with this method by having a [2, 300, 300] array and working modulo 2, but even that is unnecessarry. By the way the transitions are calcualted, you only need a 300x300 2D array to do the DP.
Besides, I think that the pure O(N2) version is shorter to code and even simpler to understand. Take a look at my code for a better understanding.
I think I misunderstood you. Can you explain your pure O(N2) ?
Btw, I know it's not necessary to use O(N3) memory. What I was trying to say was that having 2-dimensional array doesn't mean that recurrence relation has 2 variables.
UPD: I just saw your new comment. While I was writing my answer I didn't see your last comment. I was mentioning what you wrote in you first comment, that's why I said recurrence relation is wrong. Sorry for confusion :/
If DPi, j, k is the number of ways to pay i dollars using j coins from the first k types of coins, then instead of doing DPi, j, k = DPi, j, k - 1 + DPi - k, j - 1, k, you just use a 2D array DPi, j, iterate first by k and do DPi, j = DPi, j + DPi - k, j - 1. If you pay attention, it's essentially the same. You're iterating by k first, so DPi, j is actually DPi, j, k - 1 from the 3D version, and you're adding DPi - k, j - 1, which is DPi - k, j - 1, k from the 3D version.
When I mean pure O(N2), I'm talking about pure quadratic for memory. Clearly, the runtime will always be O(N3).