Stone Game III
Hard · Dynamic Programming · Array · Math · Dynamic Programming · Game Theory
Problem
Stones lie in a row, and stoneValue[i] is the value of stone i, which may be negative. Alice and Bob take turns, Alice first.
On a turn, a player takes 1, 2 or 3 stones from the front of the row and adds their values to their score. The game ends when every stone has been taken, and the higher score wins.
If both play optimally, return "Alice" if Alice wins, "Bob" if Bob wins, or "Tie" if the scores are equal.
Examples
Input: stoneValue = [5,-1,-2,4] Output: "Alice"
Alice takes only the 5. Bob's best reply is all three remaining stones (net 1), so Alice wins 5 to 1.
Input: stoneValue = [-1,-1,-1] Output: "Bob"
Alice must take at least one negative stone; whatever she does, Bob ends ahead.
Input: stoneValue = [1,2,3,6] Output: "Tie"
If Alice takes 1, 2 and 3 (6), Bob takes the 6. Any shorter first move lets Bob take the rest including the 6, so a tie is her best.
Constraints
- 1 <= len(stoneValue) <= 5 · 10^4
- -1000 <= stoneValue[i] <= 1000
Approaches
- Top-down recursion with memoization — time O(n), space O(n)
Follow-up
If a turn may take up to k stones, the same recurrence has k choices: O(n · k). If each turn could take from either end of the row, the state becomes an interval [i, j] and the DP becomes O(n²).
Related problems
Start free on Cariara · Coding problems · System design studio
