Game DP — optimal strategy for a game, coin game winner
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
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].