Minimum score possible for a player by selecting one or two consecutive array elements from given binary array | Java program for the above approach ; Stores the minimum score for each states as map < pair < pos , myturn > , ans > ; Function to find the minimum score after choosing element from array ; Return the stored state ; Base Case ; Player A 's turn ; Find the minimum score ; Store the current state ; Return the result ; Player B 's turn ; Find minimum score ; Store the current state ; Return the result ; Function that finds the minimum penality after choosing element from the given binary array ; Starting position of choosing element from array ; 0 denotes player A turn 1 denotes player B turn ; Function Call ; Function to print the answer ; Minimum penalty ; Calculate sum of all arr elements ; Print the minimum score ; Driver code
import java . io . * ; import java . util . * ; class GFG { static class R { int x , y ; public R ( int x , int y ) { this . x = x ; this . y = y ; } } static HashMap < R , Integer > m = new HashMap < > ( ) ; public static int findMinimum ( int [ ] arr , int N , int pos , int turn ) { R x = new R ( pos , turn ) ; if ( m . containsKey ( x ) ) { return m . get ( x ) ; } if ( pos >= N - 1 ) { return 0 ; } if ( turn == 0 ) { int ans = Math . min ( findMinimum ( arr , N , pos + 1 , 1 ) + arr [ pos ] , findMinimum ( arr , N , pos + 2 , 1 ) + arr [ pos ] + arr [ pos + 1 ] ) ; R v = new R ( pos , turn ) ; m . put ( v , ans ) ; return ans ; } if ( turn != 0 ) { int ans = Math . min ( findMinimum ( arr , N , pos + 1 , 0 ) , findMinimum ( arr , N , pos + 2 , 0 ) ) ; R v = new R ( pos , turn ) ; m . put ( v , ans ) ; return ans ; } return 0 ; } public static int countPenality ( int [ ] arr , int N ) { int pos = 0 ; int turn = 0 ; return findMinimum ( arr , N , pos , turn ) + 1 ; } public static void printAnswer ( int [ ] arr , int N ) { int a = countPenality ( arr , N ) ; int sum = 0 ; for ( int i = 0 ; i < N ; i ++ ) { sum += arr [ i ] ; } System . out . println ( a ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 } ; int N = 8 ; printAnswer ( arr , N ) ; } }