Dice Throw | DP | C ++ program to find number of ways to get sum ' x ' with ' n ' dice where every dice has ' m ' faces ; 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 program to test above functions
#include <iostream> NEW_LINE #include <string.h> NEW_LINE using namespace std ; int findWays ( int m , int n , int x ) { int table [ n + 1 ] [ x + 1 ] ; for ( int j = 1 ; j <= m && j <= x ; j ++ ) table [ 1 ] [ j ] = 1 ; for ( int i = 2 ; i <= n ; i ++ ) for ( int j = 1 ; j <= x ; j ++ ) for ( int k = 1 ; k <= m && k < j ; k ++ ) table [ i ] [ j ] += table [ i - 1 ] [ j - k ] ; return table [ n ] [ x ] ; } int main ( ) { cout << findWays ( 4 , 2 , 1 ) << endl ; cout << findWays ( 2 , 2 , 3 ) << endl ; cout << findWays ( 6 , 3 , 8 ) << endl ; cout << findWays ( 4 , 2 , 5 ) << endl ; cout << findWays ( 4 , 3 , 5 ) << endl ; return 0 ; }