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
< ? php function optimalStrategyOfGame ( $ arr , $ n ) { $ table = array_fill ( 0 , $ n , array_fill ( 0 , $ n , 0 ) ) ; for ( $ gap = 0 ; $ gap < $ n ; ++ $ gap ) { for ( $ i = 0 , $ j = $ gap ; $ j < $ n ; ++ $ i , ++ $ j ) { $ x = ( ( $ i + 2 ) <= $ j ) ? $ table [ $ i + 2 ] [ $ j ] : 0 ; $ y = ( ( $ i + 1 ) <= ( $ j - 1 ) ) ? $ table [ $ i + 1 ] [ $ j - 1 ] : 0 ; $ z = ( $ i <= ( $ j - 2 ) ) ? $ table [ $ i ] [ $ j - 2 ] : 0 ; $ table [ $ i ] [ $ j ] = max ( $ arr [ $ i ] + min ( $ x , $ y ) , $ arr [ $ j ] + min ( $ y , $ z ) ) ; } } return $ table [ 0 ] [ $ n - 1 ] ; } $ arr1 = array ( 8 , 15 , 3 , 7 ) ; $ n = count ( $ arr1 ) ; print ( optimalStrategyOfGame ( $ arr1 , $ n ) . " " ) ; $ arr2 = array ( 2 , 2 , 2 , 2 ) ; $ n = count ( $ arr2 ) ; print ( optimalStrategyOfGame ( $ arr2 , $ n ) . " " ) ; $ arr3 = array ( 20 , 30 , 2 , 2 , 2 , 10 ) ; $ n = count ( $ arr3 ) ; print ( optimalStrategyOfGame ( $ arr3 , $ n ) . " " ) ; ? >