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 <= 301 <= 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);
}
}
Input
n = 1, k = 6, target = 3
Output
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]
}
Input
n = 1, k = 6, target = 3
Output
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]
Input
n = 2, k = 6, target = 7
Output
6