Question about memory reduction in Dynamic Programming problem
Difference between en1 and en2, changed 289 character(s)
Hello,  ↵

I was trying to solve [problem:383E]. Using the technique described here: https://codeforces.net/blog/entry/45223  ↵


I managed to get AC here: [submission:61233188] using regular memory reduction (Reducing one of the dimensions to the size of 2).  ↵
I don't understand how it can be reduced to one-dimensional like this: [submission:61233599].  ↵

Here is an image 
(with my amazing paint skills :P) to demonstrate my understanding of the dp dependencies in this problem: [![ ](https://ibb.co/F61FkKd)Untitled.png](https://www.imageupload.net/upload-image/2019/09/24/Untitled.png)](https://www.imageupload.net/image/z41S)  ↵


I can't see how these updates are done in the solution with only one dimension.  ↵

Any help would be appreciated.  ↵
Thanks.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Bekh 2019-09-24 20:52:21 289 Tiny change: 'roblem:![ ](https://' -> 'roblem:![ ss](https://' (published)
en1 English Bekh 2019-09-24 20:41:14 536 Initial revision (saved to drafts)