# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Name |
---|
300^4 complexity will definitely not get you accepted. Lose the loop inside the dp state, convert the loop into two state calls as taking the current coin and not taking it. Also, why are you clearing dp array for each case? You only need to do it once. For 'tot' parameter in dp state, you went backwards. Do the same for 'term' parameter.
Hmm.. Thanks.
But I m not clear with recursion's complexity.
Ok, crux of it goes like this: the number of parameters you have for a single dp state, multiply their worst cast limit together. Plus if you have inside loops inside the dp state, those factor in too. You have 3 parameters here, namely 'ind', 'tot' and 'term' whose maximum values can be 300. So we get 300^3 by multiplying them. You also have a loop going on inside the dp state which adds an iteration of 300 at most. That's how you get 300^4 or O(N^4) complexity.