#1872
Stone Game VIII
candidate master · 1325 · lc hard +32 · verified · 54% accepted · 474 likes · top 46%
Description
Alice and Bob alternate turns (Alice first) in a stone game. There are n stones in a row. On each turn while more than one stone remains, the current player:
- Picks some x > 1 and removes the leftmost x stones.
- Adds their combined value to their own score.
- Places a new stone on the left with value equal to that sum.
The game ends when one stone remains. Alice aims to maximize (Alice's score - Bob's score); Bob aims to minimize it. Return the score difference when both play optimally.
Example 1:
Input: stones = [-1,2,-3,4,-5]
Output: 5
Explanation:
- Alice removes the first 4 stones, adds (-1) + 2 + (-3) + 4 = 2 to her score, and places a stone of
value 2 on the left. stones = [2,-5].
- Bob removes the first 2 stones, adds 2 + (-5) = -3 to his score, and places a stone of value -3 on
the left. stones = [-3].
The difference between their scores is 2 - (-3) = 5.
Example 2:
Input: stones = [7,-6,5,10,5,-2,-6]
Output: 13
Explanation:
- Alice removes all stones, adds 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 to her score, and places a
stone of value 13 on the left. stones = [13].
The difference between their scores is 13 - 0 = 13.
Example 3:
Input: stones = [-10,-12]
Output: -22
Explanation:
- Alice can only make one move, which is to remove both stones. She adds (-10) + (-12) = -22 to her
score and places a stone of value -22 on the left. stones = [-22].
The difference between their scores is (-22) - 0 = -22.
Code
1
2
3