1025. Divisor Game

class Solution:
    def divisorGame(self, N: int) -> bool:
        dp = [False for i in range(N+1)]
        for i in range(N+1):
             for j in range(1, i//2 + 1):
                    if i % j == 0 and (not dp[i - j]):
                        dp[i] = True
                        break
        return dp[N]

1. Initialize solution as false till (N+1). N+1 because index 0 is ignored.
2. Outer Loop (index i) from 1 to N (inclusive) and fill up the table till n. At the end, we will return dp[n] as answer
3. Inner loop (index j) finds the divisor for index i. We only need to find divisor up to i//2 because a number j greater than i//2 can't give i%j==0
4. Once we find an index j that divides i, we got a j that Alice can pick but is that optimal? It is optimal if i-j is not losing for Alice, meaning when Bob gets i-j dp[i-j] must be False. When both these conditions are met we set dp[i]=True.
5. We break the loop because we only need to find one such j that can make Alice win the game.

출처: leetcode.com/problems/divisor-game/discuss/274727/Python-DP