DDSA Solutions

1406. Stone Game III

HardView on LeetCode
ArrayMathDynamic ProgrammingGame Theory

Problem Overview

Alice and Bob take 1, 2, or 3 piles from the front of the remaining row, both optimally.

Intuition

Alice and Bob take 1, 2, or 3 piles from the front of the remaining row, both optimally. Track a relative score: stones the current player collects minus the best relative score the opponent can force on what is leftover. Working from the end, each start index tries all three take sizes and keeps the best gap. Alice wins if the gap from index 0 is positive, Bob if negative, else Tie.

Algorithm

  1. 1Let dp[n] = 0. Fill dp[i] for i = n-1 down to 0 as int.MinValue/2 initially.
  2. 2From i, sum = 0; for j = i..min(i+2, n-1): sum += stoneValue[j]; dp[i] = max(dp[i], sum - dp[j+1]).
  3. 3score = dp[0]; return "Alice" / "Bob" / "Tie" by comparing score to 0.

Example Walkthrough

Input: stoneValue = [1, 2, 3, 6]

  1. 1.From the end, each position stores the best relative take of 1-3 piles.
  2. 2.Optimal play leaves equal totals for Alice and Bob, so score = 0.

Output: Tie

Common Pitfalls

  • •Seed unused dp slots with a very small value so the first candidate assignment is not blocked by 0.
  • •Take at most three piles and never past n - guard the inner loop with j < n.
  • •Positive / negative / zero score maps to Alice / Bob / Tie - do not use absolute stone totals alone.
  • •This is relative score DP, not an absolute sum for one player only.
1406.cs
C#
// Approach: Bottom-up DP from the end. dp[i] is the best relative score
// (stones taken minus opponent's best from the remainder) starting at i, when
// the current player may take 1, 2, or 3 piles. Try each take size, add the
// prefix sum of taken piles, subtract dp[j+1], keep the max. Compare dp[0]
// to decide Alice / Bob / Tie.
// Complexity: O(n) time and O(n) space.
public class Solution
{
    public string StoneGameIII(int[] stoneValue)
    {
        int n = stoneValue.Length;
        // dp[i] := the maximum relative score Alice can make with stoneValue[i..n)
        int[] dp = new int[n + 1];
        Array.Fill(dp, int.MinValue / 2, 0, n);
        dp[n] = 0;

        for (int i = n - 1; i >= 0; --i)
        {
            int sum = 0;
            for (int j = i; j < i + 3 && j < n; ++j)
            {
                sum += stoneValue[j];
                dp[i] = Math.Max(dp[i], sum - dp[j + 1]);
            }
        }

        int score = dp[0];
        return score > 0 ? "Alice" : score < 0 ? "Bob" : "Tie";
    }
}
Was this solution helpful?

Related Problems