Dice Roll


  • 0
    S

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


  • 0

    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.


  • 2
    L

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

Log in to reply
 

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