Hints — p79 Stone Game II

Hint 1. Game DP from CURRENT-PLAYER POV (not Alice-specific). State (i, M) = piles remaining + parameter. dp[i][M] = max stones current player gets from this state.

Hint 2. Suffix sum identity: if current player takes x piles starting at i, total remaining sum is suf[i]. Opponent then plays optimally and gets dp[i+x][max(M,x)] for themselves. So current player gets suf[i] - dp[i+x][max(M,x)]. The middle terms cancel.

Hint 3. Recurrence: dp[i][M] = max over x in 1..min(2M, n-i) of (suf[i] - dp[i+x][max(M,x)]). Don’t forget M = max(M, x) per game rule.

Hint 4. Base cases: i == n → 0 (no piles). 2M >= n - i → take everything, dp[i][M] = suf[i]. M can be capped at n (since 2M ≥ n always suffices).

Hint 5. Fill order: iterate i from n down to 0; M from 1 to n. Or use top-down memoization. Answer: dp[0][1].

If stuck: see solution.py.