Mr.Struggler's blog

By Mr.Struggler, history, 5 weeks 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  

»
5 weeks 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.