Bottom up solution

#1

please provide me with bottom up code of this problem with detailed explanation of your own.
Don’t suggest other links.

#2

Top Down approach is better for this question.
I will help you in forming the recurrence relations.
Coins can be picked from either end. So we will have two values - one when coin is picked from the start and the other when coin is picked from the end. And we will return the maximum of the two values.
Let the two values be a and b, v be our array and s and e be the starting and ending indices respectively (s = 0 and e = n-1 initially).
maxvalue is the function name.
a = v[s] + min( maxvalue(v,s+2,e), maxvalue(v,s+1,e-1) );
b = v[e] + min( maxvalue(v,s+1,e-1), maxvalue(v,s,e-2) );
a is the value when the first player picks the coin from the start. So v[s] is added. Our array is from s+1 to e now. If the second player picks from the start, our search space becomes s+2 to e now and the first player will be left with maxvalue(v,s+2,e). And if he picks from the end, our search space becomes s+1 to e-1 and the first player will be left with maxvalue(v,s+1,e-1). Both players play optimally, so the second player will leave the minimum of the two values for the first player. Hence the first recurrence relation for a.
We can form the second recurrence relation for b similarly.
And finally we will return max(a,b).
Try to code this approach and tell me if you are able to get correct answer.

#3

bro i got this solution earlier but facing some problem in bottom solution.Please provide me with bottom up explanation

#4

Bottom up solution is not required then. It is important to solve a problem using one approach only. Others will lead to confusion. Plus this question is best solved using top down approach only.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.