# Number of Dice Rolls With Target Sum

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