Shouldnt my recursive relation look some thing like this?

#1

forward phase:

dpf[i] = max ( arr[i+1]+func(i+2,j) , arr[i+2]+func(i+3,j) )

backward phase:

dpb[i]=max( arr[i-1]+func(i-2,j) ,arr[i-2]+func(i-3,j) )

at the end we can return dpf[k]+dpb[k]
in the backward case i am traversing in reverse direction

#2

Hey @neha_153, your DP issue is arising due to incorrect indexing.
you should add arr[i] and call for i+1 and i+2,
also final answer will not be

as there are some points covered twice (both in forward and backward movement)
lets say starting from k you go till x and then return back to 1
so here answer is dpf[k]+dpb[x], what my point is that region from k to x is covered twice which is not accounted by your final answer.
Also try doing this in single one approach (make you function like it automatically returns)

#3

as u mentioned …it is right arr[i]+the rest

#4

the rest of the code is fine?

#5

and i have accounted from region k to x becoz once i go till k to x and then i traverse back from n-1 to 1 so it is added twice

#6

Yes or share your code if still facing problem

#7


can u correct this code…i think there is some problem with the base case.

#8

Hey Neha!,
I see same issues as discussed earlier


you can refer to my code (I’ve commented the logic for better understanding)
If you have any issue then you may ask further.

#9

this is one of the best ways somebody has explained the code …both top down and bottom up…thanks for the effort…will definetely mark 5 star for this effort

#10


i tired implementing but dp array is turning out to be bit diff

#11

This is because in top-down approach only the required states are calculated while in bottom up we calculate all!

#12

at this point what can i do to the code to get it accepted?

#13

the code I sent you is accepted! you have to code bottom up DP as top down will result in run error(due to stack memory overflow)

#14

ok
thanks i ll try submiting it