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