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
- Define
dp[i]as the best score difference (current player minus opponent) obtainable from the suffix starting ati. - Taking
kstones (withkin1..3) yieldssum(stoneValue[i..i+k-1]) - dp[i+k], because the opponent then moves fromi+k. - So
dp[i]is the maximum over the three choices, withdp[n] = 0. - 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
bestwith 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.