| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | cry | 160 |
| 2 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | atcoder_official | 158 |
| 5 | awoo | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 149 |
I've been trying DP questions ( not enough in codeforces, but in leetcode ) and whenever I try to solve this question, I'm stuck at whether I should do it with 1d Array or 2d Array.
now now now, I know many of you are going to say solve more problems ( I agree ). Through this question, I just want to know perspective of someone who has done dozens of questions..
Thanks and Peace out :)
If you have only one changing DP state — you use 1D array, otherwise 2D+ array.
It should be obvious if you know DP
Perfect.
1)It depends on your definition of dp: whichever definition is more convenient for you to calculate, that's the one you'll continue to use. As an example can serve this problem from atcoder dp contest. You can define there theoretically 2D recurrent function, but with 1D it is easier to calculate (I don't know a solution which passes the test cases with a 2D dp, only 1D).
2)Another situation could be when the MLE / TLE is tight and you need to reduce the number of parameters to pass the test cases. As an example can serve this problem from USACO december contest 2018, where 2D precomputation / dp throws MLE.