Rocket Academy Divisor Game Solution

# https://leetcode.com/problems/divisor-game/
class Solution:

    def __init__(self):
        # Keys will be value of N
        # Values will be can curr_player win
        self.cache = {}

    def determine_if_alice_can_win(self, N, curr_player):
        # Base case
        # If N and curr_player in cache, return cached value
        if N in self.cache:
            if curr_player == 0:
                if self.cache[N] == True:
                    return True
                return False

            # If curr player is Bob
            if self.cache[N] == True:
                return False
            return True

        # If N is 1, current player loses
        if N == 1:
            if curr_player == 0:
                return False
            return True

        # For each number num between 1 and N/2 inclusive:
        for num in range(1, N//2 + 1):
            # Skip if N is not multiple of num
            if N % num != 0:
                continue

            # If N is multiple of num: Recurse and tell me if Alice can win if curr player chooses num
            next_player = (curr_player + 1) % 2
            can_alice_win = self.determine_if_alice_can_win(N-num, next_player)

            # If calculation is not in cache yet, add it to the cache
            if N-num not in self.cache:
                if next_player == 0:
                    self.cache[N-num] = can_alice_win
                else:
                    self.cache[N-num] = not can_alice_win

            # If current player is Alice AND Alice can win, return True
            if curr_player == 0 and can_alice_win:
                return True

            # If current player is Bob AND Alice CANNOT win for any 1 of the values of num, return False
            if curr_player == 1 and not can_alice_win:
                return False

        # If current player is Alice and she hasn't won yet, return False
        if curr_player == 0:
            return False

        # If current player is Bob and Alice hasn't lost yet, return True
        if curr_player == 1:
            return True

    def divisorGame(self, N: int) -> bool:
        # Return whether A wins for original N
        # Player 0 represents A, Player 1 represents B
        return self.determine_if_alice_can_win(N, 0)