Блог пользователя Adiix

[NEWBIE QUESTION] How do you decide whether you're going to use 1d or 2d Array in DP?

Автор Adiix, история, 2 года назад, По-английски

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

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

If you have only one changing DP state — you use 1D array, otherwise 2D+ array.

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

It should be obvious if you know DP

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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.

→ Ответить