Optimal Game Strategy..One Test case is not correct
This is a dynamic programming question and you have used a greedy approach for solving it. So, although it may seem like taking max at every level is the optimal approach, that may not always be the case. Try running your code for the test case
4
8 15 3 7
The optimal answer would be 22 but your approach would give 15!
Yeah ,Okay…i got it…Thank you so much…Can you provide a hint for the same problem using dynamic programming??
Dynamic programming is basically just an optimization to save time, so you should try coming up with a recursive solution first. Here your solution would make calls for all possible solutions and return the best one. Try making a recursion tree on paper and exploring the choices the players would have, and observing how they would choose.
After that, if you find over-lapping sub-problems, you can use DP approach to store their sub-solutions instead of calculating them every time.
Since you have not responded for a long time now, I am marking this doubt as resolved. If you still have queries about this, you can open the doubt again.
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.