## [f]izzbuzzer

### 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[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];
}
}
```