Stone Game III

hard array math dp game theory

Problem

Stones in a row with values. Two players alternate; each turn take 1, 2, or 3 stones from the left. Both play optimally; return 'Alice', 'Bob', or 'Tie'.

InputstoneValue = [1,2,3,7]

Output"Bob"

Alice plays first but Bob can always end up with the 7.

stoneValue

def stone_game_iii(stoneValue):
    n = len(stoneValue)
    dp = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        take, best = 0, float('-inf')
        for k in range(1, 4):
            if i + k > n: break
            take += stoneValue[i + k - 1]
            best = max(best, take - dp[i + k])
        dp[i] = best
    if dp[0] > 0: return "Alice"
    if dp[0] < 0: return "Bob"
    return "Tie"

function stoneGameIII(v) {
  const n = v.length;
  const dp = new Array(n + 1).fill(0);
  for (let i = n - 1; i >= 0; i--) {
    let take = 0, best = -Infinity;
    for (let k = 1; k <= 3 && i + k - 1 < n; k++) {
      take += v[i + k - 1];
      best = Math.max(best, take - dp[i + k]);
    }
    dp[i] = best;
  }
  return dp[0] > 0 ? "Alice" : dp[0] < 0 ? "Bob" : "Tie";
}

class Solution {
    public String stoneGameIII(int[] v) {
        int n = v.length;
        int[] dp = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            int take = 0, best = Integer.MIN_VALUE;
            for (int k = 1; k <= 3 && i + k - 1 < n; k++) {
                take += v[i + k - 1];
                best = Math.max(best, take - dp[i + k]);
            }
            dp[i] = best;
        }
        return dp[0] > 0 ? "Alice" : dp[0] < 0 ? "Bob" : "Tie";
    }
}

string stoneGameIII(vector& v) {
    int n = v.size();
    vector dp(n + 1, 0);
    for (int i = n - 1; i >= 0; i--) {
        int take = 0, best = INT_MIN;
        for (int k = 1; k <= 3 && i + k - 1 < n; k++) {
            take += v[i + k - 1];
            best = max(best, take - dp[i + k]);
        }
        dp[i] = best;
    }
    return dp[0] > 0 ? "Alice" : dp[0] < 0 ? "Bob" : "Tie";
}

Explanation

Two players alternate, each taking 1, 2, or 3 stones from the left, and both play optimally. Instead of tracking each player's score separately, the slick idea is to track the score difference from the perspective of whoever is about to move.

dp[i] means: starting at position i, the best (my score − opponent's score) the current player can guarantee. We fill it backwards so that the future positions dp[i+k] are already known.

For each starting index i we try taking k = 1, 2, 3 stones. We add their values into take, and the opponent then plays optimally from i+k, securing their own lead dp[i+k]. From our viewpoint that flips sign, so our value is take - dp[i+k], and we keep the maximum.

Example: stoneValue = [1,2,3,7]. No matter what Alice grabs first, Bob can always end up with the 7 and finish ahead, so dp[0] comes out negative and the answer is "Bob".

Finally we read dp[0]: positive means Alice wins, negative means Bob, and zero is a Tie. One linear pass does it all.

Time: O(n) Space: O(n)