Coins In a Line Game

Problem

In front of you is a row of N coins, with values v_1, v_2, ..., v_n.

You are asked to play the following game. You and an opponent take turns choosing either the first or last coin from the row, removing it from the row, and receiving the value of the coin.

Write a program that returns the maximum amount of money you can win with certainty, if you move first, assuming your opponent plays optimally.

In this game, Alice and Bob take turns removing coins from either end of a line of n coins, where each coin has a specific value. Both players aim to collect coins such that the total value of their set is maximized. Alice starts first, and both players play optimally, always considering the best possible choices to secure the highest total value while leaving the worst options for their opponent.

Your task is to compute the maximum sum of values Alice can guarantee herself, assuming both Alice and Bob pick coins using optimal strategies.

Examples

Example 1

1
2
3
4
5


Input: nums = [1, 2, 3, 4]
Output: 6
Explanation: 
- You pick 4 (first move), opponent picks 3, then you pick 2.
- Your score = 4 + 2 = 6, opponent's score = 3 + 1 = 4.

Example 2

1
2
3
4
5


Input: nums = [8, 15, 3, 7]
Output: 22
Explanation: 
- You pick 7 (first move), opponent picks 15, then you pick 8.
- Your score = 7 + 8 = 22, opponent's score = 15 + 3 = 18.

Solution

Method 1 - Using DP

Reasoning

Dynamic Programming Approach: The problem is not as simple as greedy decision-making where you always pick the coin with the largest value at the ends. Since your opponent also plays optimally to minimise your final score, you need to anticipate their moves in every situation. This makes it a perfect candidate for dynamic programming, where decisions are made based on smaller sub-problems.
Anticipating Moves: At every step, you must evaluate both possible options (taking the first or last coin from the line) and factor in the best move your opponent will make next. By simulating the opponent’s optimal decisions, you can determine the maximum score you are guaranteed to collect from the entire line of coins.
Core Formula (Recurrence Relation):
- Let dp[i][j] represent the maximum value you can secure when working with the subarray of coins between index i and j inclusively:
  - Option 1: Choose the first coin at index i:
    - You gain the value of the first coin (nums[i]), but your opponent will then select the move that minimises your future options.
    - Result: nums[i] + min(dp[i+2][j], dp[i+1][j-1])
  - Option 2: Choose the last coin at index j:
    - You gain the value of the last coin (nums[j]), while your opponent similarly minimises your options.
    - Result: nums[j] + min(dp[i+1][j-1], dp[i][j-2])
- Here is how we can visualize it.
- Combine both options and take the maximum value:
  1 2
  
  dp[i][j] = max(nums[i] + min(dp[i+2][j], dp[i+1][j-1]), nums[j] + min(dp[i+1][j-1], dp[i][j-2]))
Base cases:
- When there is only one coin left (i == j), the result is simply dp[i][i] = nums[i].
- For two coins remaining (i + 1 == j), the result is dp[i][j] = max(nums[i], nums[j]).

Approach

Use a 2D dp array where dp[i][j] stores the maximum value you can secure from coins between indices i and j.
Build the table dp iteratively, starting with the smallest sub-problems:
- For diagonal elements (one coin), dp[i][i] = nums[i].
- For two coins, choose the maximum: dp[i][j] = max(nums[i], nums[j]).
For larger subarrays, evaluate using the above recurrence relation.
Finally, return dp[0][n-1], representing the best value you can collect for the whole array.

Since the optimal choice at every step depends on the minimised future value (your opponent’s strategy), this approach guarantees that you win the maximum possible amount irrespective of your opponent’s moves.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


class Solution {

    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];

        // Fill the dp table
        for (int length = 1; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                // Base cases
                if (i == j) {
                    dp[i][j] = nums[i];
                } else {
                    int leftPick =
                        nums[i] +
                        Math.min(
                            i + 2 <= j ? dp[i + 2][j] : 0,
                            i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0
                        );
                    int rightPick =
                        nums[j] +
                        Math.min(
                            i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0,
                            i <= j - 2 ? dp[i][j - 2] : 0
                        );
                    dp[i][j] = Math.max(leftPick, rightPick);
                }
            }
        }
        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = { 8, 15, 3, 7 };
        System.out.println(solution.maxCoins(nums)); // Output: 22
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution:
    def maxCoins(self, nums):
        n = len(nums)
        # Initialize dp array
        dp = [[0] * n for _ in range(n)]
        
        # Fill the dp array
        for length in range(1, n+1):  # Subarrays of length 1 to n
            for i in range(n - length + 1):
                j = i + length - 1
                # Base cases
                if i == j:
                    dp[i][j] = nums[i]
                else:
                    # Calculate dp[i][j] using the recurrence relation
                    left_pick = nums[i] + min(dp[i+2][j] if i+2 <= j else 0, 
                                        dp[i+1][j-1] if i+1 <= j-1 else 0)
                    right_pick = nums[j] + min(dp[i+1][j-1] if i+1 <= j-1 else 0, 
                                            dp[i][j-2] if i <= j-2 else 0)
                    dp[i][j] = max(left_pick, right_pick)
        
        return dp[0][n-1]


# Example usage
nums = [8, 15, 3, 7]
print(Solution().maxCoins(nums))  # Output: 22

Complexity

⏰ Time complexity: O(n^2): We fill an n x n table.
🧺 Space complexity: O(n^2): The 2D dp array stores results for all subarrays.

Problem#

Examples#

Example 1#

Example 2#

Solution#

Method 1 - Using DP#

Reasoning#

Approach#

Code#

Complexity#