⚡Flashcard Drill➔
NeetCode #698LC-1406Hard1-D Dynamic ProgrammingNC 250
← Back to All Problems

#698 · #1406 · Stone Game III(石子游戏 III)

📌 Problem Statement & Constraints

Alice and Bob play with a row of stones stoneValue. Starting with Alice, each player takes 1, 2, or 3 stones from the front and adds their values to that player's score; both play optimally. Return "Alice", "Bob", or "Tie". Constraints: 1 <= stoneValue.length <= 5 * 10^4, -1000 <= stoneValue[i] <= 1000.

💡 Core Algorithmic Approaches

  1. Define dp[i] as the best score difference (current player minus opponent) obtainable from the suffix starting at i.
  2. Taking k stones (with k in 1..3) yields sum(stoneValue[i..i+k-1]) - dp[i+k], because the opponent then moves from i+k.
  3. So dp[i] is the maximum over the three choices, with dp[n] = 0.
  4. The sign of dp[0] decides the outcome: positive for Alice, negative for Bob, zero for a tie.

💻 Benchmark Python3 Implementation

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        dp = [0] * (n + 1)             # dp[i] = best (current - opponent) from i
        for i in range(n - 1, -1, -1):
            best = float("-inf")
            take = 0
            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"

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one backward pass with a constant factor of three.
💾 Space Complexity
O(n): the dp array.

⚠️ Interview Pitfalls & Follow-ups

  • Tracking two absolute scores: the difference formulation collapses them into one array and is much simpler.
  • Using + dp[i+k]: the opponent's advantage must be subtracted, since the roles swap each turn.
  • Seeding best with 0: values may be negative, so the initial best must be negative infinity.
  • Returning the score instead of a name: the contract asks for the winner as a string.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems