Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Problem Link - http://www.iarcs.org.in/inoi/2011/zco2011/zco2011-1b.php

The task is to find the maximum score you can get in the game. Such problems, based on games, where you have to simulate, predict the result, or obtain the maximum possible score always seem to puzzle me.

I can do it with recursion by considering two cases - first number picked or last number picked, each of which again branches into two states similarly, and so on... which finally can yield the max possible result.

But it's a very time-inefficient approach, since time increases exponentially, due to the large test cases.

What is the most pragmatic approach to the problem, and to such problems in general?

share|improve this question
6  
Hi, we aren't here to do all the work for you. What have you already tried? –  Yannis Rizos Nov 6 '12 at 18:49
    
Strange! I try several problems, & only post the ones here which I find difficult. As I said in the question, I have no idea on how to solve such game based questions, so I don't know where to start! –  7Aces Nov 6 '12 at 18:52
3  
Please update your question to give us more details on your attempt to solve the problem, for example why you think your solution is time inefficient. –  Yannis Rizos Nov 6 '12 at 19:27
    
@YannisRizos Can I simply say that such problems stump me? :P –  7Aces Nov 6 '12 at 19:32
1  
Perfect. Easy, wasn't it? Thanks. –  Yannis Rizos Nov 6 '12 at 19:38

1 Answer 1

up vote 5 down vote accepted

The trick is thus:
Consider 2,5,3,3,2,1.

Your move: Pick Left
Opponent move: Pick Right
Current state: 5,3,3,2.

vs.

Your move: Pick Right
Opponent move: Pick Left
Current state: 5,3,3,2.

Using recursion, you will end up calculating how many more points you can get for 5,3,3,2 twice!

So, the solution is to use memoization (dynamic programming)

The first time you call your function on 5,3,3,2, store the score for that (e.g., in a two dimensional array where the first index is how many numbers have been removed from the left and the second index is how many numbers have been removed from the right). The next time you are about to call it, just load the score from the previous time.

A nice benefit of this strategy is that you can use your existing recursive algorithm with only minimal modification.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.