169. Stone Game

Medium · Dynamic Programming

Alice and Bob play a game with piles of stones arranged in a row. There are an even number of piles, and the total number of stones is odd (so there are no ties). Alice and Bob take turns, with Alice going first. On each turn, a player takes the entire pile from either the leftmost or rightmost end of the row. The player with the most stones at the end wins.

Both players play optimally. Given an array `piles` where `piles[i]` is the number of stones in the i-th pile, return `true` if Alice wins, or `false` if Bob wins.

Note: Because the number of piles is even and the total is odd, there is always a winner (no ties). Alice always wins with optimal play — but your solution should demonstrate this via dynamic programming or game theory reasoning.

Examples

Example 1
Input: piles = [5, 3, 4, 5]
Output: true
Explanation: Alice starts by taking the 5 from the right. Bob takes 5 from the left. Alice takes 4 from the right. Bob takes 3. Alice has 5+4=9, Bob has 5+3=8. Alice wins.
Example 2
Input: piles = [3, 7, 2, 3]
Output: true
Explanation: Alice can always guarantee more stones than Bob with optimal play. Alice wins.

Constraints