Optimal Strategy for the Divisor game using Dynamic Programming | Java 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
import java . util . * ; class GFG { static int divisorGame ( int N , int A , int dp [ ] [ ] ) { if ( N == 1 N == 3 ) return 0 ; if ( N == 2 ) return 1 ; 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 == 1 ) ans |= divisorGame ( N - i , 0 , dp ) ; else ans &= divisorGame ( N - i , 1 , dp ) ; } } return dp [ N ] [ A ] = ans ; } public static void main ( String [ ] args ) { 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 " ) ; } }