Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 1140 Stone Game II - Key Idea

Track M parameter

Unlike Predict the Winner, we can't just track indices. The value of MM affects what moves are legal. Two positions with the same remaining piles but different MM are different states.

State: dp[i][M]dp[i][M] = max stones current player can get starting from pile ii with parameter MM. Also useful: precompute suffix sums. If I know total stones from pile ii onward, and I know what opponent gets, my stones = total - opponent's stones.