Estrategia Óptima para el juego del Divisor usando Programación Dinámica

Dado un número entero N y dos jugadores, A y B están jugando un juego. En el turno de cada jugador, ese jugador hace un movimiento restando un divisor de N actual (que es menor que N) de N actual, formando así una nueva N para el próximo turno . El jugador que no le queda ningún divisor para restar pierde el juego. La tarea es decir qué jugador gana el juego si el jugador A toma el primer turno, asumiendo que ambos jugadores juegan de manera óptima.
Ejemplos:
 

Entrada: N = 2 
Salida: el jugador A gana 
Explicación: 
el jugador A elige 1 y B no tiene más movimientos.
Entrada: N = 3 
Salida: el jugador B gana 
Explicación: 
el jugador A elige 1, el jugador B elige 1 y A no tiene más movimientos. 
 

Enfoque:
este problema mencionado anteriormente se puede resolver utilizando la programación dinámica. 
 

• Tomaremos un DP que tiene 2 estados, es decir 
   

N -> número actual a la izquierda 
A -> valor booleano para decidir si es el turno del jugador A o no

 

•  
• En cada estado, intentaremos encontrar todos los divisores de N e intentaremos encontrar el siguiente estado en el que el jugador actual está ganando. Para el jugador A, intentaremos encontrar el siguiente estado donde el valor devuelto sea verdadero, mientras que para el jugador B, intentaremos encontrar el siguiente estado donde el valor devuelto sea falso (ya que falso representa la pérdida del jugador A).
• Los casos base serán para N=1 donde siempre perderá el jugador A y N=2 donde siempre perderá el jugador B.
• Para encontrar la respuesta, solo necesitamos encontrar el valor de DP[ N ][ 1 ].

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program for implementation of
// Optimal Strategy for the Divisor
// Game using Dynamic Programming
#include <bits/stdc++.h>
using namespace std;
 
// Recursive function to find the winner
bool divisorGame(int N, bool A, int dp[][2])
{
 
    // check if N=1 or N=3 then player B wins
    if (N == 1 or N == 3)
        return false;
 
    // check if N=2 then player A wins
    if (N == 2)
        return true;
 
    // check if current state already visited
    // then return the previously obtained ans
    if (dp[N][A] != -1)
        return dp[N][A];
 
    // check if currently it is player A's turn
    // then initialise the ans to 0
    int ans = (A == 1) ? 0 : 1;
 
    // Traversing across all the divisors of N
    // which are less than N
    for (int i = 1; i * i <= N; i++) {
 
        // check if current value of
        // i is a divisor of N
        if (N % i == 0) {
 
            // check if it is player A's turn
            // then we need at least one true
            if (A)
                ans |= divisorGame(N - i, 0, dp);
 
            // Else if it is player B's turn
            // then we need at least one false
            else
                ans &= divisorGame(N - i, 1, dp);
        }
    }
 
    // Return the current ans
    return dp[N][A] = ans;
}
 
// Driver code
int main()
{
    // initialise N
    int N = 3;
 
    int dp[N + 1][2];
 
    memset(dp, -1, sizeof(dp));
 
    if (divisorGame(N, 1, dp) == true)
        cout << "Player A wins";
    else
        cout << "Player B wins";
 
    return 0;
}

// Java program for implementation of
// optimal strategy for the divisor
// game using dynamic programming
 
import java.util.*;
 
class GFG {
 
    // Recursive function to find the winner
    static int divisorGame(int N, int A, int dp[][]) {
 
        // Check if N = 1 or N = 3 then player B wins
        if (N == 1 || N == 3)
            return 0;
 
        // Check if N = 2 then player A wins
        if (N == 2)
            return 1;
 
        // Check if current state already visited
        // then return the previously obtained ans
        if (dp[N][A] != -1)
            return dp[N][A];
 
        // Check if currently it is player A's turn
        // then initialise the ans to 0
        int ans = (A == 1) ? 0 : 1;
 
        // Traversing across all the divisors of N
        // which are less than N
        for (int i = 1; i * i <= N; i++) {
 
            // Check if current value of
            // i is a divisor of N
            if (N % i == 0) {
 
                // Check if it is player A's turn
                // then we need at least one true
                if (A == 1)
                    ans |= divisorGame(N - i, 0, dp);
 
                // Else if it is player B's turn
                // then we need at least one false
                else
                   ans &= divisorGame(N - i, 1, dp);
            }
        }
 
        // Return the current ans
        return dp[N][A] = ans;
    }
 
    // Driver code
    public static void main(String[] args) {
         
        // Initialise N
        int N = 3;
 
        int[][] dp = new int[N + 1][2];
 
        for (int i = 0; i < N + 1; i++) {
             for (int j = 0; j < 2; j++) {
                  dp[i][j] = -1;
            }
        }
 
        if (divisorGame(N, 1, dp) == 1)
            System.out.print("Player A wins");
        else
            System.out.print("Player B wins");
 
    }
}
 
// This code contributed by sapnasingh4991

# Python3 program for implementation of
# Optimal Strategy for the Divisor
# Game using Dynamic Programming
 
from math import sqrt
 
# Recursive function to find the winner
def divisorGame(N,A,dp):
    # check if N=1 or N=3 then player B wins
    if (N == 1 or N == 3):
        return False
 
    # check if N=2 then player A wins
    if (N == 2):
        return True
 
    # check if current state already visited
    # then return the previously obtained ans
    if (dp[N][A] != -1):
        return dp[N][A]
 
    # check if currently it is player A's turn
    # then initialise the ans to 0
    if(A == 1):
        ans = 0
    else:
        ans = 1
 
    # Traversing across all the divisors of N
    # which are less than N
    for i in range(1,int(sqrt(N))+1,1):
        # check if current value of
        # i is a divisor of N
        if (N % i == 0):
            # check if it is player A's turn
            # then we need at least one true
            if (A):
                ans |= divisorGame(N - i, 0, dp)
 
            # Else if it is player B's turn
            # then we need at least one false
            else:
                ans &= divisorGame(N - i, 1, dp)
 
    dp[N][A] = ans
 
 
    # Return the current ans
    return dp[N][A]
 
# Driver code
if __name__ == '__main__':
    # initialise N
    N = 3
 
    dp = [[-1 for i in range(2)] for j in range(N+1)]
 
    if (divisorGame(N, 1, dp) == True):
        print("Player A wins")
    else:
        print("Player B wins")
 
# This code is contributed by Surendra_Gangwar

// C# program for implementation of
// optimal strategy for the divisor
// game using dynamic programming
using System;
 
class GFG {
 
// Recursive function to find the winner
static int divisorGame(int N, int A,
                       int [,]dp)
{
 
    // Check if N = 1 or N = 3
    // then player B wins
    if (N == 1 || N == 3)
        return 0;
 
    // Check if N = 2 then player A wins
    if (N == 2)
        return 1;
 
    // Check if current state already visited
    // then return the previously obtained ans
    if (dp[N, A] != -1)
        return dp[N, A];
 
    // Check if currently it is player A's turn
    // then initialise the ans to 0
    int ans = (A == 1) ? 0 : 1;
 
    // Traversing across all the divisors of N
    // which are less than N
    for(int i = 1; i * i <= N; i++)
    {
         
       // Check if current value of
       // i is a divisor of N
       if (N % i == 0)
       {
            
           // Check if it is player A's turn
           // then we need at least one true
           if (A == 1)
               ans |= divisorGame(N - i, 0, dp);
                
           // Else if it is player B's turn
           // then we need at least one false
           else
              ans &= divisorGame(N - i, 1, dp);
       }
    }
     
    // Return the current ans
    return dp[N, A] = ans;
}
 
// Driver code
public static void Main(String[] args)
{
     
    // Initialise N
    int N = 3;
    int[,] dp = new int[N + 1, 2];
     
    for(int i = 0; i < N + 1; i++)
    {
       for(int j = 0; j < 2; j++)
       {
          dp[i, j] = -1;
       }
    }
     
    if (divisorGame(N, 1, dp) == 1)
    {
        Console.Write("Player A wins");
    }
    else
    {
        Console.Write("Player B wins");
    }
}
}
 
// This code is contributed by amal kumar choubey

<script>
// Javascript program for implementation of
// Optimal Strategy for the Divisor
// Game using Dynamic Programming
 
 
// Recursive function to find the winner
function divisorGame(N, A, dp) {
 
    // check if N=1 or N=3 then player B wins
    if (N == 1 || N == 3)
        return false;
 
    // check if N=2 then player A wins
    if (N == 2)
        return true;
 
    // check if current state already visited
    // then return the previously obtained ans
    if (dp[N][A] != -1)
        return dp[N][A];
 
    // check if currently it is player A's turn
    // then initialise the ans to 0
    let ans = (A == 1) ? 0 : 1;
 
    // Traversing across all the divisors of N
    // which are less than N
    for (let i = 1; i * i <= N; i++) {
 
        // check if current value of
        // i is a divisor of N
        if (N % i == 0) {
 
            // check if it is player A's turn
            // then we need at least one true
            if (A)
                ans |= divisorGame(N - i, 0, dp);
 
            // Else if it is player B's turn
            // then we need at least one false
            else
                ans &= divisorGame(N - i, 1, dp);
        }
    }
 
    // Return the current ans
    return dp[N][A] = ans;
}
 
// Driver code
 
// initialise N
let N = 3;
 
let dp = [];
 
for (let i = 0; i < N + 1; i++) {
    let temp = [-1]
    for (let j = 0; j < 2; j++) {
        temp.push([-1])
    }
    dp.push(temp)
}
 
// memset(dp, -1, sizeof(dp));
 
if (divisorGame(N, 1, dp) == true)
    document.write("Player A wins");
else
    document.write("Player B wins");
 
// This code is contributed by gfgking
</script>

Player B wins