Maximum Profit- Memoization,DP,optimality

Question

I was practicing the problem on Algorithm games , I tried the following problem but couldn't find the efficient way to do it::

So can you please help me.Here is the problem.

This is the exact link:: http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm228

Answer 1

Let dp[i, j] = maximum profit alice can make for the coints i, ... j.

We have:

dp[i, i] = input[i] for all 1 <= i <= N
dp[i, i + 1] = max(input[i], input[i + 1])
dp[i, j] = max(// take first coin, opponent will minimize your next move
               input[i] + min(dp[i + 2, j], dp[i + 1, j - 1]),
               // take last coin, opponent will still minimize your next move
               input[j] + min(dp[i, j - 2], dp[i - 1, j - 1]))

Answer 2

You can solve it using dynamic programming. State can be represented by:

set of available coins,
whos turn it is

For each state you should compute maximal amount of money that person in turn can win.

Hint: Rules of this game allow to describe set of available coins as interval.

@edit

for(int interval_size = 1; interval_size <= n; interval_size++) {
    for(int interval_start = 0; interval_start + interval_size <= n; interval_start++) {
         // result[interval_start][interval_start + interval_size] depends only on
         // -> result[interval_start][interval_start + interval_size - 1]
         // -> result[interval_start + 1][interval_start + interval_size]
    }
}