Game Theory DP
You've optimized single-player decisions. Now handle two players taking turns. Solve Stone Game variants where both sides play to win.
Lessons
1. Introduction to Game Theory DP
Two players, optimal play
2. When to Use Game Theory DP
Alternating turns, perfect info
3. Problem - Stone Game IV
LC 1510 - remove square amounts
4. Stone Game IV - Why Naive Fails
Winning if opponent can lose
5. Stone Game IV - Defining the DP
dp[n] = can current player win?
6. Stone Game IV - Transition
Try all squares, find losing state
7. Stone Game IV - Base Cases
dp[0]=false, dp[1]=true, dp[2]=false
8. Stone Game IV - Implementation
O(n√n) checking squares
9. Stone Game IV - Time and Space
√n moves per position
10. Problem - Stone Game III
LC 1406 - take 1, 2, or 3
11. Stone Game III - Why Naive Fails
Maximize score difference
12. Stone Game III - Defining the DP
dp[i] = advantage from position i
13. Stone Game III - Transition
Take stones, subtract opponent's best
14. Stone Game III - Base Cases
dp[n] = 0, no stones left
15. Stone Game III - Implementation
Right to left, O(n)
16. Stone Game III - Time and Space
O(1) space with sliding window
17. Nim Game - Overview
XOR piles, zero = lose
18. Nim Game - Why Naive Fails
XOR trick explained
19. Nim Game - Defining the DP
Grundy = mex of reachable states
20. Nim Game - Core Logic
mex = minimum excludant
21. Lessons from Nim Game
XOR Grundy for combined games
22. Staircase Nim - Why Odd Steps Matter
23. Staircase Nim - Winning Strategy
24. Staircase Nim - Problem Pattern
Odd steps only matter
25. Staircase Nim - Implementation
Even-to-odd = adding to Nim
26. Composite Games - Sprague-Grundy Theorem
XOR Grundy numbers
27. Computing Grundy Numbers
mex of reachable Grundy values
28. Game on DAG - Applying Grundy
Topological order on DAG
29. Problem - Stone Game I
LC 877 - pick from ends
30. Stone Game I - Solution
Interval DP or math trick
31. Stone Game I - One-Liner
Alice always wins (odd total)
32. Problem - Stone Game VII
LC 1690 - score = remaining sum
33. Stone Game VII - Solution
Remove stone, score the rest
34. Stone Game VII - Implementation
Prefix sums for range totals
35. Quiz: Game Theory Patterns
Which game pattern is this?
36. Quiz: Game Theory Edge Cases
Single pile, symmetric games
37. Common Mistakes in Game Theory DP
Whose turn? Score difference handles it
38. Problem - Cat and Mouse
LC 913
39. Cat and Mouse - Implementation
Solution approach
40. Problem - Stone Game VIII
LC 1872
41. Stone Game VIII - Implementation
Solution approach
42. Problem - Grundy's Game
CSES 2207
43. Grundy's Game - Implementation
Solution approach
44. Section Recap
From win/lose to Grundy