# Dice Roll

• When m dices with n faces are rolled together, find the number of ways the sum of the faces is k.

• Although it looks complex at first sight, it seems to be a pretty simple dynamic programming problem with o(nmk) complexity.

DP(i, j) = sum_{w=1}^n DP(i-1, j - w)

where i is the number of dices (up to m) and j the target number (up to k). The base cases are DP(0, *) = 0, DP(*, 0) = 0, DP(1, w) = 1 if 1 <= w <= n and 0 otherwise.

• @sinma

A simple Java Solution as below:

``````public static int findWays(int dices, int faces, int sum) {
//Skip not reachable cases: sum is too low or too high
if (sum < faces /*min value*/ || sum > dices * faces /*max value*/) return -1;

// Create a table to store results of subproblems.  One extra
// row and column are used for simplicity (Number of dices
// 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 = new int[dices + 1][sum + 1];

// Table entries for only one dices
for (int i = 1; i <= faces && i <= sum; i++)
table[1][i] = 1;

// Fill rest of the entries in table using recursive relation
// i: number of dices, j: sum
for (int d = 2; d <= dices; d++) {
for (int s = 1; s <= sum; s++) {
/*
table[dices][sum]
=    table[dices-1][sum -1]  -- find 1+(sum-1) from (dices-1) dices
+ table[dices-1][sum-2]   -- find 2+(sum-2) from (dices-1) dices
+ table[dices-1][sum-3]   -- find 2+(sum-3) from (dices-1) dices
+ ...
+ table[dices-1][sum-faces]
*/
for (int f = 1; f <= faces && f < s; f++)
table[d][s] += table[d - 1][s - f];
}
}
return table[dices][sum];
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.