Game Theory¶
Table of Contents¶
- 292. Nim Game (Easy)
- 1025. Divisor Game (Easy)
- 3227. Vowels Game in a String (Medium)
- 2038. Remove Colored Pieces if Both Neighbors are the Same Color (Medium)
- 877. Stone Game (Medium)
- 1510. Stone Game IV (Hard)
- 486. Predict the Winner (Medium)
- 1690. Stone Game VII (Medium)
- 1686. Stone Game VI (Medium)
- 1927. Sum Game (Medium)
- 1406. Stone Game III (Hard)
- 1140. Stone Game II (Medium)
- 1563. Stone Game V (Hard)
- 464. Can I Win (Medium)
- 2029. Stone Game IX (Medium)
- 810. Chalkboard XOR Game (Hard)
- 1872. Stone Game VIII (Hard)
- 913. Cat and Mouse (Hard)
- 1728. Cat and Mouse II (Hard)
- 294. Flip Game II (Medium) 👑
- 1908. Game of Nim (Medium) 👑
- 2005. Subtree Removal Game with Fibonacci Tree (Hard) 👑
- 2868. The Wording Game (Hard) 👑
292. Nim Game¶
1025. Divisor Game¶
"""
- Return `True` if Alice wins the game, assuming both players play optimally.
- `dp[n]` stores the result of the game when the number is `n`.
- Initialize `dp[1] = False`.
"""
# DP
def divisorGameDP(n: int) -> bool:
if n <= 1:
return False
dp = [False for _ in range(n + 1)]
for i in range(2, n + 1):
for j in range(1, i):
if i % j == 0 and not dp[i - j]:
dp[i] = True
break
return dp[n]
# Math
def divisorGameDPMath(n: int) -> bool:
return n % 2 == 0
# |-------------|-----------------|--------------|
# | Approach | Time | Space |
# |-------------|-----------------|--------------|
# | DP | O(n^2) | O(n) |
# | Math | O(1) | O(1) |
# |-------------|-----------------|--------------|
n = 2
print(divisorGameDP(n)) # True
print(divisorGameDPMath(n)) # True
3227. Vowels Game in a String¶
2038. Remove Colored Pieces if Both Neighbors are the Same Color¶
877. Stone Game¶
1510. Stone Game IV¶
486. Predict the Winner¶
1690. Stone Game VII¶
1686. Stone Game VI¶
1927. Sum Game¶
1406. Stone Game III¶
1140. Stone Game II¶
1563. Stone Game V¶
464. Can I Win¶
2029. Stone Game IX¶
810. Chalkboard XOR Game¶
1872. Stone Game VIII¶
913. Cat and Mouse¶
1728. Cat and Mouse II¶
-
Tags: Array, Math, Dynamic Programming, Graph, Topological Sort, Memoization, Matrix, Game Theory