Game Theory DP

Opening scenario

Problem references use LC for LeetCode.

An even number of piles sit in a row with a positive number piles[i] of stones in each pile. The total is odd, and two players alternate. Each turn a player takes the entire pile from either end. Both play optimally. Does player 1 end up with more stones (LC 877, Stone Game)? The interviewer escalates. Take 1..2M piles: a turn takes 1 to 2M piles off the front, where M is the largest take so far and starts at 1. Take 1, 2 or 3 piles off the front. Flip-game moves: on a string of + and -, a move flips ++ into --, and the player with no move loses.

The even-pile, odd-total version has a first-player winning strategy, but deriving a recurrence also prepares you for variants where that shortcut fails. Start by expressing a position’s value from the perspective of the player whose turn is next.