#1406
Stone Game III
expert · 1110 · lc hard +32 · verified · 63.3% accepted · 2,300 likes · top 66%
Description
Alice and Bob play a stone game with the integer array stoneValue. Stones lie in a row; Alice goes first. Each turn, a player takes 1, 2, or 3 stones from the front. Both play optimally to maximize their own score.
Return "Alice" if Alice wins, "Bob" if Bob wins, or "Tie" if they finish with equal scores.
Example 1:
Input: stoneValue = [1,2,3,7]
Output: "Bob"
Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.
Example 2:
Input: stoneValue = [1,2,3,-9]
Output: "Alice"
Explanation: Alice must choose all the three piles at the first move to win and leave Bob with negative score.
If Alice chooses one pile her score will be 1 and the next move Bob's score becomes 5. In the next move, Alice will take the pile with value = -9 and lose.
If Alice chooses two piles her score will be 3 and the next move Bob's score becomes 3. In the next move, Alice will take the pile with value = -9 and also lose.
Remember that both play optimally so here Alice will choose the scenario that makes her win.
Example 3:
Input: stoneValue = [1,2,3,6]
Output: "Tie"
Explanation: Alice cannot win this game. She can end the game in a draw if she decided to choose all the first three piles, otherwise she will lose.
Code
1
2
3