Hello there everyone
I am new to dynamic programming, and I would really appreciate if someone can help me on how I can approach the following problem in hacker rank:
you can see the problem description down below
Screenshot-4 — ImgBB[
^]
Right now, I am thinking of using bottom up 2D tabulation. However I am not sure about what the dimensions will represent and how I will fill in the table.
What I have tried:
Demonstration image:
Screenshot-5 — ImgBB[
^]
Let rows and columns represent row and column locations in the field. Let the cells in the table store the maximum rectangle size ending at that cell.
(1,1) = 4 maximum size rectangle so far is 4
(1,2) = 6 maximum size rectangle to the left was 4, now it is 6
(1,3) = 8 maximum size rectangle to the left was 6, now it is 8
(1,4) = 10 maximum size rectangle to the left was 8, now it is 10
(2,1) = 6 maximum size rectangle to the up was 4, now including this is 6
(2,2) = 6 maximum size rectangle to the up was 6, now including this is 8
The (2,2) in this case is incorrect. Because it should have been 6. The reason why it is incorrect is because the cell above (1,2) was storing the maximum size of a rectangle that goes from (1,1) till (1,2)