Help needed in understanding memoization in this problem

Revision en1, by Darshann, 2021-05-28 09:32:06

1389B - Array Walk

I have recently started learning dp so I am only practicing writing memoized solutions rather than bottom-up dp. I had written a recursive solution for this problem but was not able to figure out the states for memoization as too many variables were changing k, z, etc. But after looking at some other submissions, I found out it was only enough to take the state to be curr_ind, z. I believed the state should include variables which are changing in transitions but here it's not the case and I am very confused.

Can someone please explain it to me how can we decide these states? TIA.

My submission: 117537731

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Darshann 2021-05-28 09:32:06 718 Initial revision (published)