Game Theory DP
You've used DP for optimization. Game Theory DP handles two players taking turns with optimal moves.
Lessons
1. Intro
The Goal
2. Vocabulary - Optimal Play
Both play perfectly
3. Winning and Losing States
The foundation
4. Quiz: Winning vs Losing
State classification
5. The Minimax Principle
My best against their best
6. Quiz: Minimax Basics
Knowledge check
7. LeetCode 486 Predict the Winner - Problem Statement
LeetCode 486
8. LeetCode 486 Predict the Winner - Key Idea
Score difference trick
9. LeetCode 486 Predict the Winner - State Design
Dp[i][j] for range
10. LeetCode 486 Predict the Winner - Transition
Left or right choice
11. LeetCode 486 Predict the Winner - Implementation
The code
12. LeetCode 486 Predict the Winner - Walkthrough
Tracing the game
13. Challenge: First Player Advantage
When does first move help?
14. Quiz: Predict the Winner
Knowledge check
15. LeetCode 1140 Stone Game II - Problem Statement
LeetCode 1140
16. LeetCode 1140 Stone Game II - Key Idea
Track M parameter
17. LeetCode 1140 Stone Game II - State Design
Dp[i][M]
18. LeetCode 1140 Stone Game II - Implementation
With suffix sums
19. LeetCode 1140 Stone Game II - Walkthrough
Tracing with M parameter
20. Challenge: Stone Game Variants
Exploring modifications
21. Quiz: Stone Game II
Knowledge check
22. LeetCode 464 Can I Win - Problem Statement
LeetCode 464
23. LeetCode 464 Can I Win - Key Idea
Bitmask meets game theory
24. LeetCode 464 Can I Win - State Design
Dp[mask]
25. LeetCode 464 Can I Win - Implementation
Memoization with bitmask
26. LeetCode 464 Can I Win - Walkthrough
Tracing with bitmask
27. Quiz: Can I Win State
Understanding the bitmask
28. Quiz: Can I Win
Knowledge check
29. Lessons from Game Theory DP
summary
30. Nim Game - Problem Statement
The classic game
31. Nim Game - Mathematical Insight
Beyond brute force
32. Divisor Game - Problem Statement
Division-based moves
33. Quiz: Divisor Game Pattern
Proving the pattern
34. Stone Game IV - Problem Statement
Perfect square moves
35. Stone Game IV - Implementation
Efficient computation
36. Flip Game II - Problem Statement
String transformation game
37. Sprague-Grundy Introduction
Combining independent games
38. Quiz: Sprague-Grundy Basics
Understanding nimbers
39. Cat and Mouse - Problem Statement
Two-agent chase
40. Cat and Mouse - Implementation
Handling draws
41. Quiz: Game with Draws
Three outcomes
42. Pattern - Game Theory DP
Recognizing and solving
43. Challenge: Non-Zero-Sum Games
Beyond win/lose
44. Challenge: More Than Two Players
Multi-agent games
45. What's Next
Preview of Probability DP
46. Section Recap
What we learned
Practice Problems
Foundational minimax game theory with optimal play
Classic minimax DP with variable M parameter
Teaches optimal play and game-ending conditions
Covered with full walkthrough in this section.
Alternate picking from piles. Greedy insight when one pile dominates.
Two-player game on palindrome string. Analysis of symmetric vs asymmetric cases.
Build lexicographically smallest string. Game-like decision at each step.
Move token on permutation. DP on DAG to determine winning positions.
Subtract 1 or divide by k. Grundy number analysis with special structure.
Count paths with subtract or divide moves. DP with harmonic sums.
Transform array to geometric sequence. Minimize total changes optimally.
First player always wins with even piles. Math insight or interval DP.
Take 1 to 2M piles, M grows. Minimax DP with expanding parameter.
Take 1-3 stones from front. Classic minimax with suffix DP.
Remove square number stones. Sprague-Grundy with perfect squares.
Split row, keep smaller half. Interval DP maximizing Alice score.
Classic stone game - determine winner with optimal play. Foundation for game theory DP.
Two-player deque game - interval DP meets game theory. Maximize your score difference.