Adiix's blog

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

By Adiix, history, 2 years ago, In English

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

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

It should be obvious if you know DP

→ Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

→ Reply