Dice Throw | DP | The main function that returns number of ways to get sum ' x ' with ' n ' dice and ' m ' with m faces . ; Create a table to store results of subproblems . One extra row and column are used for simpilicity ( Number of dice is directly used as row index and sum is directly used as column index ) . The entries in 0 th row and 0 th column are never used . ; Table entries for only one dice ; Fill rest of the entries in table using recursive relation i : number of dice , j : sum ; Return value ; Driver Code
< ? php function findWays ( $ m , $ n , $ x ) { $ table ; for ( $ i = 1 ; $ i < $ n + 1 ; $ i ++ ) for ( $ j = 1 ; $ j < $ x + 1 ; $ j ++ ) $ table [ $ i ] [ $ j ] = 0 ; for ( $ j = 1 ; $ j <= $ m && $ j <= $ x ; $ j ++ ) $ table [ 1 ] [ $ j ] = 1 ; for ( $ i = 2 ; $ i <= $ n ; $ i ++ ) for ( $ j = 1 ; $ j <= $ x ; $ j ++ ) for ( $ k = 1 ; $ k <= $ m && $ k < $ j ; $ k ++ ) $ table [ $ i ] [ $ j ] += $ table [ $ i - 1 ] [ $ j - $ k ] ; return $ table [ $ n ] [ $ x ] ; } echo findWays ( 4 , 2 , 1 ) . " STRNEWLINE " ; echo findWays ( 2 , 2 , 3 ) . " STRNEWLINE " ; echo findWays ( 6 , 3 , 8 ) . " STRNEWLINE " ; echo findWays ( 4 , 2 , 5 ) . " STRNEWLINE " ; echo findWays ( 4 , 3 , 5 ) . " STRNEWLINE " ; ? >