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