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
def findWays ( m , n , x ) : NEW_LINE INDENT table = [ [ 0 ] * ( x + 1 ) for i in range ( n + 1 ) ] NEW_LINE for j in range ( 1 , min ( m + 1 , x + 1 ) ) : NEW_LINE INDENT table [ 1 ] [ j ] = 1 NEW_LINE DEDENT for i in range ( 2 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , x + 1 ) : NEW_LINE INDENT for k in range ( 1 , min ( m + 1 , j ) ) : NEW_LINE INDENT table [ i ] [ j ] += table [ i - 1 ] [ j - k ] NEW_LINE DEDENT DEDENT DEDENT return table [ - 1 ] [ - 1 ] NEW_LINE DEDENT print ( findWays ( 4 , 2 , 1 ) ) NEW_LINE print ( findWays ( 2 , 2 , 3 ) ) NEW_LINE print ( findWays ( 6 , 3 , 8 ) ) NEW_LINE print ( findWays ( 4 , 2 , 5 ) ) NEW_LINE print ( findWays ( 4 , 3 , 5 ) ) NEW_LINE