Divisor Game Solution

This is a classic game theory problem solved with dynamic programming. The code implements a recursive solution that determines whether the first player can win given a starting number N.

bool divisorGame(int N, bool res=false) {
    if (dp[N] != 0) return dp[N]==1;    // return precomputed result

    for(int i=1;!res && i<N;++i) { // continue while current move doesn't win
        if (N % i == 0) res = !divisorGame(N-i);    // after choosing i, opponent plays with N-i
    }

    dp[N] = res? 1 : -1;    // store result: 1 for win, -1 for loss
    return res;
}

int dp[1001] = {0};

The algorithm works by trying every possible divisor at each step. If Alice can choose a divisor such that Bob loses from the resulting position, then Alice wins. The memoization array dp stores computed results to avoid redundant calculations.

Each position gets marked as either winning (1) or losing (-1) for the current player. The recursion explores all valid moves until reaching base cases that determine the winner.

#game-theory #dynamic-programming