At 7:00 to 8:00 in Calvin's Game

#1

Sir I understood the recurrence used in forward phase, but the one for backward phase, how did we concluded that it is same as that of forward phase?

#2

@pangatt4,
Why would the recurrence change, its exactly same type of moves, just in opposite direction?

#3

Yes, we have the same moves but in opposite direction, so shouldn’t that change indices as a[i]+max(dp[i+1], dp[i+2]). (ie instead of minus, plus sign)?

#4

@pangatt4,
That depends on which direction you iterate on dp. Even I solved this with plus sign, but then you would have to iterate backwards, i.e from n to 1. You can do it it any way, that you feel more intuitive.

Here is my submission with your recurrence.

1 Like