#877

Stone Game

pupil · 590 · lc medium +29 · verified · 72.9% accepted · 3,532 likes · top 83%

Description

Alice and Bob take turns in a game involving an even number of stone piles arranged in a row. Each pile piles[i] has a positive integer number of stones. The total stones across all piles is odd, so ties are impossible.

Alice goes first. Each turn, the current player takes all the stones from either the first or last remaining pile. The player who collects the most stones wins.

Assuming both play optimally, return true if Alice wins, or false if Bob wins.

Example 1:

Input: piles = [5,3,4,5]

Output: true

Explanation:

Alice starts first, and can only take the first 5 or the last 5.

Say she takes the first 5, so that the row becomes [3, 4, 5].

If Bob takes 3, then the board is [4, 5], and Alice takes 5 to win with 10 points.

If Bob takes the last 5, then the board is [3, 4], and Alice takes 4 to win with 9 points.

This demonstrated that taking the first 5 was a winning move for Alice, so we return true.

Example 2:

Input: piles = [3,7,2,3]

Output: true

Code

1

2

3

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:

class Solution:
    def stoneGame(self, piles: List[int]) -> bool: