Skip to content

DP Game Theory

Table of Contents

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

877. Stone Game

486. Predict the Winner

1510. Stone Game IV

1690. Stone Game VII

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

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

Comments