sajalhsn13's blog

By sajalhsn13, history, 6 years ago, In English

I am trying to solve this problem. There is a tutorial but for me its not so clear. You can see that I am green. For me the state is [numberOfProgrammer][numberOfLine][maxBug] which is 500*500*500. The tutorial has a solution with state 2*500*500. It is very hard for me to understand the state elimination. Someone please explain the solution so that I(as a green) can understand.

  • Vote: I like it
  • +8
  • Vote: I do not like it

6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

This is because in dp transitions only previous state of one programmer less is needed, so this accounts for only 2 instead of 500, otherwise you'll have memory limit verdict.

only two is needed as mentioned.