Ph.D. Qual Study Assistant

1. The Problem

Given a row of `n` coins with values `v(1)...v(n)` where `n` is even, two players alternate turns. In each turn, a player selects either the first or last coin from the row. The goal is to determine the maximum amount of money you can guarantee to win if you move first, assuming the opponent also plays optimally to maximize their own score.

2. The Idea: Dynamic Programming on Subgames

This is a game theory problem that can be solved with dynamic programming. The key is to realize that any state of the game is defined by the remaining contiguous sub-array of coins. We want to find the maximum value we can get from any given sub-array.

Let `dp[i][j]` be the maximum value the current player can get from the sub-array of coins from index `i` to `j`. The opponent plays optimally, meaning they will leave you with the worst possible choice on your next turn.

If it's your turn for the sub-array `v[i...j]`, you have two choices:

1. Take coin `v[i]`: The opponent will then play on the sub-array `v[i+1...j]`. They will choose either `v[i+1]` or `v[j]` to leave you with the minimum possible value. So, after they play, you will be left to choose from `v[i+2...j]` or `v[i+1...j-1]`. The value you get is `v[i] + min(dp[i+2][j], dp[i+1][j-1])`.
2. Take coin `v[j]`: The opponent will then play on `v[i...j-1]`. They will choose to leave you with the minimum of `dp[i+1][j-1]` and `dp[i][j-2]`. The value you get is `v[j] + min(dp[i+1][j-1], dp[i][j-2])`.

Since you want to maximize your score, you choose the better of these two options. This gives the recurrence relation:

We build the solution for small sub-arrays first (length 2, 4, ...) up to `n`. The final answer is `dp[0][n-1]`.

3. The Algorithm

1. Create a 2D DP table, `dp[n][n]`, initialized to 0.
2. Iterate over the length of the sub-array, `len`, from 2 to `n` (in steps of 2).
3. For each length, iterate with `i` from 0 to `n-len`. Let `j = i + len - 1`.
4. Inside the loops, calculate the two possible outcomes for the player:
   • `val1 = v[i] + min(dp[i+2][j], dp[i+1][j-1])`
   • `val2 = v[j] + min(dp[i+1][j-1], dp[i][j-2])`
   • (Handle boundary conditions for the `min` terms carefully, e.g., if `i+2 > j`, the value is 0).
5. Set `dp[i][j] = max(val1, val2)`.
6. The final answer is `dp[0][n-1]`.

4. Complexity Analysis

Time Complexity: O(n²)

We have two nested loops to fill the DP table. The outer loop for `len` runs `n/2` times, and the inner loop for `i` runs about `n` times. Inside the loops, the calculation is O(1). This gives a total time complexity of O(n²).

Space Complexity: O(n²)

We use a 2D DP table of size `n x n` to store the intermediate results for all subproblems. This requires O(n²) additional space.