Calvin Games dynamc prgramming

#1

As been explained in the hint video, how the forward steps can be the same as backward steps.
Also please suggest me some ways to improve development of recurrence relation.

#2

Hi @Codemaniac_Aditya
steps: a b c d e f g h
Backward Steps: suppose u want to reach a from d. so u can go like d->c>b>a and many more ways. Similarly, for dis path only, u can reach from a to d using a->b->c->d.So, backward and forward steps can be considered similar.
For solving, u first need to calculate forward dp from k+1 to n using dpf[i]=A[i]+max(dpf[i-1],dpf[i-2]);
calculate dfb from 1 to n using dpb[i]=A[i]+max(dpb[i-1],dpb[i-2]).
then use ans=max(ans,dpb[i]+dpf[i]-A[i]) to find ur answer.
Hope dis helps.
If still something is unclear, post ur doubt here.

1 Like