Dynamic Programming | Set 30 (Dice Throw) | GeeksforGeeks

Given n dice each with m faces, numbered from 1 to m, find the number of ways to get sum X. X is the summation of values on each face when all the dice are thrown.

Dynamic Programming (DP).

Let the function to find X from n dice is: Sum(m, n, X)
The function can be represented as:
Sum(m, n, X) = Finding Sum (X - 1) from (n - 1) dice plus 1 from nth dice
               + Finding Sum (X - 2) from (n - 1) dice plus 2 from nth dice
               + Finding Sum (X - 3) from (n - 1) dice plus 3 from nth dice
                  ...................................................
                  ...................................................
                  ...................................................
              + Finding Sum (X - m) from (n - 1) dice plus m from nth dice

So we can recursively write Sum(m, n, x) as following
Sum(m, n, X) = Sum(m, n - 1, X - 1) + 
               Sum(m, n - 1, X - 2) +
               .................... + 
               Sum(m, n - 1, X - m)

// The main function that returns number of ways to get sum 'x'

// with 'n' dice and 'm' with m faces.

int findWays(int m, int n, int x)

{

    // 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 0th row and 0th column

    // are never used.

    int table[n + 1][x + 1];

    memset(table, 0, sizeof(table)); // Initialize all entries as 0

    // Table entries for only one dice

    for (int j = 1; j <= m && j <= x; j++)

        table[1][j] = 1;

    // Fill rest of the entries in table using recursive relation

    // i: number of dice, j: sum

    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];

    /* Uncomment these lines to see content of table

    for (int i = 0; i <= n; i++)

    {

      for (int j = 0; j <= x; j++)

        cout << table[i][j] << " ";

      cout << endl;

    } */

    return table[n][x];

}

Time Complexity: O(m * n * x) where m is number of faces, n is number of dice and x is given sum.

We can add following two conditions at the beginning of findWays() to improve performance of program for extreme cases (x is too high or x is too low)

// When x is so high that sum can not go beyond x even when we // get maximum value in every dice throw. if (m*n <= x)     return (m*n == x);   // When x is too low if (n >= x)     return (n == x);

With above conditions added, time complexity becomes O(1) when x >= m*n or when x <= n.

Read full article from Dynamic Programming | Set 30 (Dice Throw) | GeeksforGeeks