Dynamic Programming21 sections · 916 units
Open in Course

Sprague-Grundy Introduction

Combining independent games

When a game splits into independent subgames, we can solve each separately and combine with XOR. Each position has a Grundy number (nimber): 0 = losing, positive = winning. G(pos)=mex({G(next)})G(pos) = mex(\{G(next)\}) where mex = minimum excludant. For combined games: G(game1+game2)=G(game1)⊕G(game2)G(game1 + game2) = G(game1) \oplus G(game2).

If XOR is 0, current player loses. This is advanced. For most LeetCode problems, simple win/lose DP suffices. Sprague-Grundy helps with complex game structures.