Stone Game
Alice and Bob play a game with a row of n piles of stones, where n is even. The number of stones in each pile is given in piles[i].
The objective of the game is to finish with the most stones. The total number of stones across all piles is odd, so there are no ties.
Alice and Bob take turns, with Alice going first. Each turn, a player takes the entire pile from either the beginning or the end of the row. This continues until there are no more piles left.
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
Input: [3,7,2,3]
Output: true
Hints
Start by considering the base case where there are only two piles left. How would Alice choose between them to maximize her stones?
Think about how the game can be broken down into smaller subproblems. If Alice picks a pile, the remaining piles form a new subproblem where Bob plays optimally. How can you use dynamic programming to store and reuse solutions to these subproblems?
Consider the concept of "optimal substructure" and "overlapping subproblems." How can you define a recursive function `canWin(piles, left, right)` that returns the maximum difference in stones Alice can achieve over Bob for the subarray `piles[left..right]`? How would you use memoization to optimize this recursion?
Related Problems
Stone Game
Alice and Bob play a game with a row of `n` piles of stones, where `n` is even. The number of stones in each pile is given in `piles[i]`.