Skip to content

Game Theory

Table of Contents

292. Nim Game

1025. Divisor Game

  • LeetCode | LeetCode CH (Easy)

  • Tags: math, dynamic programming, brainteaser, game theory

  • 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.
1025. Divisor Game - Python Solution
# 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

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, math, dynamic programming, recursion, game theory

1690. Stone Game VII

1686. Stone Game VI

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, math, greedy, sorting, heap priority queue, game theory

1927. Sum Game

1406. Stone Game III

1140. Stone Game II

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, math, dynamic programming, prefix sum, game theory

1563. Stone Game V

464. Can I Win

  • LeetCode | LeetCode CH (Medium)

  • Tags: math, dynamic programming, bit manipulation, memoization, game theory, bitmask

2029. Stone Game IX

810. Chalkboard XOR Game

1872. Stone Game VIII

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, math, dynamic programming, prefix sum, game theory

913. Cat and Mouse

  • LeetCode | LeetCode CH (Hard)

  • Tags: math, dynamic programming, graph, topological sort, memoization, game theory

1728. Cat and Mouse II

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, math, dynamic programming, graph, topological sort, memoization, matrix, game theory

294. Flip Game II

  • LeetCode | LeetCode CH (Medium)

  • Tags: math, dynamic programming, backtracking, memoization, game theory

1908. Game of Nim

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, math, dynamic programming, bit manipulation, brainteaser, game theory

2005. Subtree Removal Game with Fibonacci Tree

  • LeetCode | LeetCode CH (Hard)

  • Tags: math, dynamic programming, tree, binary tree, game theory

2868. The Wording Game

Comments