Skip to content

Game Theory

Table of Contents

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

  • LeetCode | 力扣

  • Tags: Math, Dynamic Programming, Bit Manipulation, Memoization, Game Theory, Bitmask

2029. Stone Game IX

810. Chalkboard XOR Game

1872. Stone Game VIII

913. Cat and Mouse

  • LeetCode | 力扣

  • Tags: Math, Dynamic Programming, Graph, Topological Sort, Memoization, Game Theory

1728. Cat and Mouse II

  • LeetCode | 力扣

  • Tags: Array, Math, Dynamic Programming, Graph, Topological Sort, Memoization, Matrix, Game Theory

294. Flip Game II

1908. Game of Nim

  • LeetCode | 力扣

  • Tags: Array, Math, Dynamic Programming, Bit Manipulation, Brainteaser, Game Theory

2005. Subtree Removal Game with Fibonacci Tree

2868. The Wording Game

Comments