Optimal Strategy for a Game | DP | Returns optimal value possible that a player can collect from an array of coins of size n . Note than n must be even ; Create a table to store solutions of subproblems ; Fill table using above recursive formula . Note that the table is filled in diagonal fashion ( similar to http : goo . gl / PQqoS ) , from diagonal elements to table [ 0 ] [ n - 1 ] which is the result . ; Here x is value of F ( i + 2 , j ) , y is F ( i + 1 , j - 1 ) and z is F ( i , j - 2 ) in above recursive formula ; Driver Code
def optimalStrategyOfGame ( arr , n ) : NEW_LINE INDENT table = [ [ 0 for i in range ( n ) ] for i in range ( n ) ] NEW_LINE for gap in range ( n ) : NEW_LINE INDENT for j in range ( gap , n ) : NEW_LINE INDENT i = j - gap NEW_LINE x = 0 NEW_LINE if ( ( i + 2 ) <= j ) : NEW_LINE INDENT x = table [ i + 2 ] [ j ] NEW_LINE DEDENT y = 0 NEW_LINE if ( ( i + 1 ) <= ( j - 1 ) ) : NEW_LINE INDENT y = table [ i + 1 ] [ j - 1 ] NEW_LINE DEDENT z = 0 NEW_LINE if ( i <= ( j - 2 ) ) : NEW_LINE INDENT z = table [ i ] [ j - 2 ] NEW_LINE DEDENT table [ i ] [ j ] = max ( arr [ i ] + min ( x , y ) , arr [ j ] + min ( y , z ) ) NEW_LINE DEDENT DEDENT return table [ 0 ] [ n - 1 ] NEW_LINE DEDENT arr1 = [ 8 , 15 , 3 , 7 ] NEW_LINE n = len ( arr1 ) NEW_LINE print ( optimalStrategyOfGame ( arr1 , n ) ) NEW_LINE arr2 = [ 2 , 2 , 2 , 2 ] NEW_LINE n = len ( arr2 ) NEW_LINE print ( optimalStrategyOfGame ( arr2 , n ) ) NEW_LINE arr3 = [ 20 , 30 , 2 , 2 , 2 , 10 ] NEW_LINE n = len ( arr3 ) NEW_LINE print ( optimalStrategyOfGame ( arr3 , n ) ) NEW_LINE