Game DP — optimal strategy for a game, coin game winner

Medium

Problem

(1) Optimal strategy: coins are in a row, and two players alternately take a coin from either end. Both play optimally. Return the maximum amount the first player can guarantee. (2) Coin game winner: from a pile of n coins, a player removes 1, x or y coins per turn, and whoever takes the last coin wins. Decide whether the first player wins.

Example 1

Input:  optimal strategy [5, 3, 7, 10]
Output: 15

Take 10, then 5.

Also asked as: Optimal Strategy for a Game · Coin game winner where every player has three choices

Test cases

Case 1

Input:    [5,3,7,10]
Expected: 15

Case 2

Input:    [8,15,3,7]
Expected: 22

Case 3

Input:    [20,30,2,2,2,10]
Expected: 42

Case 4

Input:    [2,2,2,2]
Expected: 4

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Interval DP on (i, j) — you pick an end, opponent plays optimally

Time O(n²)Space O(n²)

dp[i][j] = max value the current player can guarantee from coins i..j = max( a[i] + min(dp[i+2][j], dp[i+1][j-1]), a[j] + min(dp[i+1][j-1], dp[i][j-2]) ).

function optimalGame(a) {
const n = a.length;
const dp = Array.from({ length: n }, () => new Array(n).fill(0));
for (let i = 0; i < n; i++) dp[i][i] = a[i];
for (let len = 2; len <= n; len++)
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
const takeLeft = a[i] + Math.min(i + 2 <= j ? dp[i + 2][j] : 0, i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0);
const takeRight = a[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(takeLeft, takeRight);
}
return dp[0][n - 1];
}

Coin game with a pile and moves {1, 2, 3}: player loses iff (n mod 4 === 0) for the classic Nim-like variant; in general compute win[i] = OR over moves of !win[i−move].