> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/number-of-dice-rolls-with-target-sum.md).

# Number of Dice Rolls With Target Sum

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`

```java
// O(d*target) Space & O(d*f*target) Time
class Solution {
    public int numRollsToTarget(int d, int f, int target) {
        int MOD = 1000000007;
        int[][] dp = new int[d + 1][target + 1];
        dp[0][0] = 1;
        // dp[i][j] -> how many ways can i dices sum up to j;
        for (int i = 1; i <= d; i++) {
            for (int j = 1; j <= target; j++) {
                if (j > i * f)
                    continue; // If j is larger than largest possible sum of i dices, there is no possible
                              // ways.
                else
                    for (int currentFace = 1; currentFace <= f && currentFace <= j; currentFace++)
                        dp[i][j] = (dp[i][j] + dp[i - 1][j - currentFace]) % MOD;
            }
        }
        return dp[d][target];
    }
}
// O(target) Space Solution
class Solution {
    public int numRollsToTarget(int d, int f, int target) {
        int MOD = 1000000007;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        // dp[j] -> how many ways to get sum up to j;
        for (int i = 1; i <= d; i++) {
            int[] dp2 = new int[target + 1];
            for (int j = 1; j <= target; j++) {
                if (j > i * f)
                    continue; // If j is larger than largest possible sum of i dices, there is no possible
                              // ways.
                else
                    for (int currentFace = 1; currentFace <= f && currentFace <= j; currentFace++)
                        dp2[j] = (dp2[j] + dp[j - currentFace]) % MOD;
            }
            dp = dp2;
        }
        return dp[target];
    }
}
```