309. Stone Game

MediumDynamic Programming

Alice and Bob play a game with piles of stones. There are an **even** number of piles arranged in a row, and each pile has a **positive** integer number of stones `piles[i]`. The objective of the game is to end with the most stones. The **total** number of stones across all the piles is **odd**, so there are no ties. Alice and Bob take turns, with **Alice starting first**. Each turn, a player takes the entire pile of stones either from the **beginning** or from the **end** of the row. This continues until there are no more piles left, at which point the person with the **most** stones **wins**. Assuming Alice and Bob play **optimally**, return `true` if Alice wins the game, or `false` if Bob wins.

Examples

Input: [5,3,4,5]

Output: true

Explanation: Alice can force a positive lead: taking pile 5 (left) leaves [3,4,5] where dp = 4 for Bob, netting 5 - 4 = 1 > 0. Alice wins.

Constraints

  • 2 <= piles.length <= 500
  • piles.length is even.
  • 1 <= piles[i] <= 500
  • sum(piles[i]) is odd.
Loading...

Run checks all cases above. Submit evaluates all test cases.