Optimal Strategy for a Game

Consider a row of n coins of values v_1, v_2, ..., v_n, where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it permanently, and receives the value of the coin.

Determine the maximum possible amount of money we can definitely win if we move first, assuming the opponent plays optimally to minimize our score.

Examples

Example 1

Coins: [5, 3, 7, 10]
Output: 15
Explanation:
- As first player, we choose 10. Remaining row: [5, 3, 7].
- Opponent chooses 7 (playing optimally). Remaining row: [5, 3].
- We choose 5. Remaining row: [3].
- Opponent chooses 3.
- Total for us = 10 + 5 = 15.

Example 2

Coins: [8, 15, 3, 7]
Output: 22
Explanation:
- We choose 7. Remaining row: [8, 15, 3].
- Opponent chooses 8. Remaining row: [15, 3].
- We choose 15. Remaining row: [3].
- Opponent chooses 3.
- Total for us = 7 + 15 = 22.

Dynamic Programming Recurrence

Let dp[i][j] represent the maximum value a player can collect from coin index i to index j.

If we choose coin i (the first coin), the opponent is left with [i+1..j]. The opponent can choose either i+1 or j. Since the opponent wants to minimize our remaining score:

If opponent picks i+1, we are left with dp[i+2][j].
If opponent picks j, we are left with dp[i+1][j-1].
Value for choosing coin i = v[i] + min(dp[i+2][j], dp[i+1][j-1])

If we choose coin j (the last coin), the opponent is left with [i..j-1]. The opponent can choose either i or j-1:

If opponent picks i, we are left with dp[i+1][j-1].
If opponent picks j-1, we are left with dp[i][j-2].
Value for choosing coin j = v[j] + min(dp[i+1][j-1], dp[i][j-2])

Therefore, the recurrence relation is: dp[i][j] = max( v[i] + min(dp[i+2][j], dp[i+1][j-1]), v[j] + min(dp[i+1][j-1], dp[i][j-2]) )

1. Memoization Solution (Top-Down DP)

function maxGameValueMemo(arr) {
    const n = arr.length;
    const memo = Array.from({ length: n }, () => new Array(n).fill(-1));
 
    function helper(i, j) {
        if (i > j) return 0;
        if (i === j) return arr[i];
        if (j === i + 1) return Math.max(arr[i], arr[j]);
 
        if (memo[i][j] !== -1) return memo[i][j];
 
        // Recurrence relation
        const pickFirst = arr[i] + Math.min(helper(i + 2, j), helper(i + 1, j - 1));
        const pickLast  = arr[j] + Math.min(helper(i + 1, j - 1), helper(i, j - 2));
 
        memo[i][j] = Math.max(pickFirst, pickLast);
        return memo[i][j];
    }
 
    return helper(0, n - 1);
}

2. Tabulation Solution (Bottom-Up DP)

We fill a 2D table dp of size n x n diagonally, starting from subproblems of length 2 up to n.

function maxGameValueTabulation(arr) {
    const n = arr.length;
    const dp = Array.from({ length: n }, () => new Array(n).fill(0));
 
    // Fill table for subproblems of length gap (where gap = j - i)
    for (let gap = 0; gap < n; gap++) {
        for (let i = 0, j = gap; j < n; i++, j++) {
            // Find x, y, z as defined in recurrence
            // x is dp[i+2][j]
            let x = (i + 2 <= j) ? dp[i + 2][j] : 0;
            // y is dp[i+1][j-1]
            let y = (i + 1 <= j - 1) ? dp[i + 1][j - 1] : 0;
            // z is dp[i][j-2]
            let z = (i <= j - 2) ? dp[i][j - 2] : 0;
 
            dp[i][j] = Math.max(
                arr[i] + Math.min(x, y),
                arr[j] + Math.min(y, z)
            );
        }
    }
 
    return dp[0][n - 1];
}
 
// Driver code
const coins = [8, 15, 3, 7];
console.log("Max money definitely won:", maxGameValueTabulation(coins));
// Output: Max money definitely won: 22

Complexity Analysis

Time Complexity: O(N^2)
- The nested loops for gap-based traversal solve $N \times N / 2$ states.
Space Complexity: O(N^2)
- To store the N x N 2D table.

Min Jumps to Reach End Egg Dropping Puzzle