Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Number of Dice Rolls With Target Sum

Sharing is caring!

Problem Statement
You have d dice, and each die has f faces numbered 1, 2, …, f.

Return the number of possible ways (out of fd total ways) modulo 10^9 + 7 to roll the dice so the sum of the face up numbers equals target.

Example 1

Input: d = 1, f = 6, target = 3
Output: 1
Explanation:
You throw one die with 6 faces.  There is only one way to get a sum of 3.

Example 2

Input: d = 2, f = 6, target = 7
Output: 6
Explanation:
You throw two dice, each with 6 faces.  There are 6 ways to get a sum of 7:
1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

Example 3

Input: d = 2, f = 5, target = 10
Output: 1
Explanation: 
You throw two dice, each with 5 faces.  There is only one way to get a sum of 10: 5+5.

Example 4

Input: d = 1, f = 2, target = 3
Output: 0
Explanation: 
You throw one die with 2 faces.  There is no way to get a sum of 3.

Example 5

Input: d = 30, f = 30, target = 500
Output: 222616187
Explanation: 
The answer must be returned modulo 10^9 + 7.

Constraints

1 <= d, f <= 30
1 <= target <= 1000

Solution
We use dynamic programming (DP). Let the function to find target from d dice is: sum(f, d, target).

The function can be represented as:

sum(f, d, target) = Finding sum (target - 1) from (d - 1) dice plus 1 from dth dice
+ Finding sum (target - 2) from (d - 1) dice plus 2 from dth dice
+ Finding sum (target - 3) from (d - 1) dice plus 3 from dth dice
...
+ Finding sum (target - d) from (d - 1) dice plus f from dth dice

Code

class Solution {
    private final int MOD = 1000000007;
    
    public int numRollsToTarget(int dice, int faces, int target) {
        //dp[i][j] = number of ways to have sum=j with i number of dice
        int[][] dp = new int[dice+1][target+1];
        
        for (int f=1; f<=faces; f++) {
            if (f<=target){
                dp[1][f] = 1;   
            }
        }
        
        for (int d=2; d<=dice; d++) {            
            for (int t=1; t<=target; t++) {
                for (int f=1; f<=faces; f++) {
                    if (t-f >= 0) {
                        dp[d][t] += dp[d-1][t-f];
                        dp[d][t] %= MOD;
                    }
                }
            }
        }
        
        return dp[dice][target];
    }
}