Algorithm

Problem Name: 1155. Number of Dice Rolls With Target Sum

You have `n` dice, and each die has `k` faces numbered from `1` to `k`.

Given three integers `n`, `k`, and `target`, return the number of possible ways (out of the `kn` total ways) to roll the dice, so the sum of the face-up numbers equals `target`. Since the answer may be too large, return it modulo `109 + 7`.

Example 1:

```Input: n = 1, k = 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: n = 2, k = 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: n = 30, k = 30, target = 500
Output: 222616187
Explanation: The answer must be returned modulo 109 + 7.
```

Constraints:

• `1 <= n, k <= 30`
• `1 <= target <= 1000`

Code Examples

#1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
Map map = new HashMap<>();
final int MODULO = 1000000007;
public int numRollsToTarget(int d, int f, int target) {
if (d == 0 && target == 0) {
return 1;
}
if (d == 0 || target == 0) {
return 0;
}
String key = d + "|" + target;
if (map.containsKey(key)) {
return map.get(key);
}
int res = 0;
for (int i = 1; i  < = f; i++) {
if (target >= i) {
res = (res + numRollsToTarget(d - 1, f, target - i)) % MODULO;
}
else {
break;
}
}
map.put(key, res);
return map.get(key);
}
}
``````
Copy The Code &

Input

cmd
n = 1, k = 6, target = 3

Output

cmd
1

#2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const numRollsToTarget = function(d, f, target) {
const mod = 10 ** 9 + 7
if (target > d * f || target < d) {
return 0
}
const dp = new Array(target + 1).fill(0)
for (let i = 1; i  <  Math.min(f + 1, target + 1); i++) {
dp[i] = 1
}
for (let i = 2; i  <  d + 1; i++) {
for (let j = Math.min(target, i * f); j > i - 1; j--) {
dp[j] = 0
for (let k = Math.max(i - 1, j - f); k  <  j; k++) {
dp[j] = (dp[j] + dp[k]) % mod
}
}
}

return dp[target]
}
``````
Copy The Code &

Input

cmd
n = 1, k = 6, target = 3

Output

cmd
1

#3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def numRollsToTarget(self, d: int, f: int, target: int) -> int:
mod = 10 ** 9 + 7
dp = [[0 for j in range(target + 1)] for i in range(d + 1)]
dp[0][0] = 1
for i in range(d):
for ff in range(1, f + 1):
for sm in range(target):
if sm + ff <= target:
dp[i + 1][sm + ff] += dp[i][sm]
dp[i + 1][sm + ff] %= mod
return dp[d][target]
``````
Copy The Code &

Input

cmd
n = 2, k = 6, target = 7

Output

cmd
6