Log inSign up
hardGeeksforGeeksNot Started

Optimal Strategy for a Game

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

You are given an array of n coins of values arr[0..n-1], where n is even. The coins are arranged in a row.

Two players play a turn-based game. In each turn, a player can pick either the first coin or the last coin of the row.

Both players are equally intelligent and play optimally to maximize their own total winnings.

Determine the maximum possible amount of money the first player can definitely win.

### Example 1 - Input: arr = [5, 3, 7, 10] - Output: 15 - Explanation: The user picks 10 (last). The opponent is left with [5, 3, 7] and picks 7. The user picks 5. Total = 10 + 5 = 15.

### Example 2 - Input: arr = [8, 15, 3, 7] - Output: 22 - Explanation: The user picks 7 (last). Opponent picks 8. User picks 15. Total = 7 + 15 = 22.

Constraints:

  • 2 <= n <= 1000
  • n is even
  • 1 <= arr[i] <= 106

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model Minimax turn-based games using dynamic programming.
  • Understand the dual max-min formulation for adversarial play.
  • Tabulate interval DP with step size 2.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Two-player turn-based game picking from endpoints of an array.
  • Both players play optimally (Minimax game theory).

Algorithmic Decision Tree:

  • dp[i][j] represents max value from sub-array arr[i..j].
  • Interval length increases by 2 each turn (since each round uses 2 coins).

Connected Patterns:

Predict the WinnerStone GameMatrix Chain Multiplication

1. Recursive Minimax Tree

Intuition

Recursively explore both choices (first and last coin), assuming the opponent plays to minimize our gain.

Algorithm

  1. Define solve(i, j).
  2. If i > j, return 0.
  3. If i == j, return arr[i].
  4. If i + 1 == j, return max(arr[i], arr[j]).
  5. Pick arr[i]: val1 = arr[i] + min(solve(i+2, j), solve(i+1, j-1)).
  6. Pick arr[j]: val2 = arr[j] + min(solve(i+1, j-1), solve(i, j-2)).
  7. Return max(val1, val2).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int i, int j, const vector<int>& arr) {
9 if (i > j) return 0;
10 if (i == j) return arr[i];
11 if (i + 1 == j) return max(arr[i], arr[j]);
12
13 int takeLeft = arr[i] + min(solve(i + 2, j, arr), solve(i + 1, j - 1, arr));
14 int takeRight = arr[j] + min(solve(i + 1, j - 1, arr), solve(i, j - 2, arr));
15
16 return max(takeLeft, takeRight);
17 }
18public:
19 int maximumAmount(vector<int>& arr, int n) {
20 return solve(0, n - 1, arr);
21 }
22};
23
24int main() {
25 Solution sol;
26 vector<int> arr = {5, 3, 7, 10};
27 cout << "Max Amount: " << sol.maximumAmount(arr, 4) << endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) call stack

2. Memoized Top-Down DP

Intuition

Use a 2D memo table of size n x n to cache interval states.

Algorithm

  1. Initialize memo[n][n] with -1.
  2. In solve(i, j): return memo[i][j] if already computed.
  3. Evaluate takeLeft and takeRight using opponent min transitions.
  4. Store and return memo[i][j].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int i, int j, const vector<int>& arr, vector<vector<int>>& memo) {
9 if (i > j) return 0;
10 if (i == j) return arr[i];
11 if (i + 1 == j) return max(arr[i], arr[j]);
12 if (memo[i][j] != -1) return memo[i][j];
13
14 int takeLeft = arr[i] + min(solve(i + 2, j, arr, memo), solve(i + 1, j - 1, arr, memo));
15 int takeRight = arr[j] + min(solve(i + 1, j - 1, arr, memo), solve(i, j - 2, arr, memo));
16
17 return memo[i][j] = max(takeLeft, takeRight);
18 }
19public:
20 int maximumAmount(vector<int>& arr, int n) {
21 vector<vector<int>> memo(n, vector<int>(n, -1));
22 return solve(0, n - 1, arr, memo);
23 }
24};
25
26int main() {
27 Solution sol;
28 vector<int> arr = {5, 3, 7, 10};
29 cout << "Max Amount: " << sol.maximumAmount(arr, 4) << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n^2) memo table + O(n) call stack

3. Iterative Bottom-Up Tabulation

Intuition

Tabulate interval lengths from 1 to n. Smaller ranges must be computed before larger ranges.

Algorithm

  1. Initialize dp[n][n] with 0.
  2. Loop gap gap from 0 to n - 1:
  3. For i = 0 to n - gap - 1:
  4. j = i + gap.
  5. x = (i + 2 <= j) ? dp[i + 2][j] : 0.
  6. y = (i + 1 <= j - 1) ? dp[i + 1][j - 1] : 0.
  7. z = (i <= j - 2) ? dp[i][j - 2] : 0.
  8. dp[i][j] = max(arr[i] + min(x, y), arr[j] + min(y, z)).
  9. Return dp[0][n - 1].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int maximumAmount(vector<int>& arr, int n) {
10 vector<vector<int>> dp(n, vector<int>(n, 0));
11
12 for (int gap = 0; gap < n; ++gap) {
13 for (int i = 0, j = gap; j < n; ++i, ++j) {
14 int x = ((i + 2) <= j) ? dp[i + 2][j] : 0;
15 int y = ((i + 1) <= (j - 1)) ? dp[i + 1][j - 1] : 0;
16 int z = (i <= (j - 2)) ? dp[i][j - 2] : 0;
17
18 dp[i][j] = max(arr[i] + min(x, y), arr[j] + min(y, z));
19 }
20 }
21
22 return dp[0][n - 1];
23 }
24};
25
26int main() {
27 Solution sol;
28 vector<int> arr = {5, 3, 7, 10};
29 cout << "Max Amount: " << sol.maximumAmount(arr, 4) << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n^2)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive MinimaxO(2^n)O(n)Exhaustive exploration of turn decisions.Subproblem recomputation
2.Memoized DPO(n^2)O(n^2)Cache interval states [i, j].Table allocation
3.Iterative Bottom-Up DPOptimalO(n^2)O(n^2)Tabulate interval gaps from 0 to n - 1.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Greedy approach (always picking the larger of arr[i] and arr[j]): Fails when picking a smaller coin exposes a massive coin to the opponent.

Pitfall 2:

Incorrect bounds when accessing i + 2 or j - 2 (must check index validity).

Crucial Edge Cases to Validate:

  • n = 2: Only two coins; first player simply picks max(arr[0], arr[1]).
  • All coins equal: First player gets exactly n / 2 * coin_value.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Be ready to demonstrate why greedy fails: give the counterexample [8, 15, 3, 7] where picking 8 greedily exposes 15 to the opponent, losing the game.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we take the MINIMUM between the outcomes of opponent's moves, but MAXIMUM of our own choices?

Back to DSA Sheet