##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1155.html

# 1155. Number of Dice Rolls With Target Sum (Medium)

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

Related Topics:
Dynamic Programming

## Solution 1. DP Top-down

Let dp[i][t] be the number of dice rolls with i dices and t target sum.

dp[i][t] = sum( dp[i-1][t-j] | 1 <= j <= f )

dp[i][t] = 0 if t < d || t > d * f

dp[1][t] = 1 if 1 <= t <= f

// OJ: https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/
// Time: O(DFT)
// Space: O(DT)
class Solution {
vector<unordered_map<int, int>> m;
long mod = 1e9+7;
int dfs(int d, int f, int target) {
if (target < d || target > d * f) return 0;
if (d == 1) return 1;
if (m[d].count(target)) return m[d][target];
long cnt = 0;
for (int j = 1; j <= f && j <= target; ++j) {
int c = dfs(d - 1, f, target - j);
cnt = (cnt + c) % mod;
}
return m[d][target] = cnt;
}
public:
int numRollsToTarget(int d, int f, int target) {
m.assign(d + 1, {});
return dfs(d, f, target);
}
};


## Solution 2. DP Top-down with Optimization

dp[i][t] = sum( dp[i-1][t-j] | 1 <= j <= f )

dp[i][t] = dp[i-1][t-1] + dp[i-1][t-2] + ... + dp[i-1][t-f]
dp[i][t-1] =              dp[i-1][t-2] + ... + dp[i-1][t-f] + dp[i-1][t-f-1]

dp[i][t] = dp[i][t-1] + dp[i-1][t-1] - dp[i-1][t-f-1]

// OJ: https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/
// Time: O(DT)
// Space: O(DT)
class Solution {
vector<unordered_map<int, int>> m;
long mod = 1e9+7, f;
int dfs(int d, int target) {
if (target < d || target > d * f) return 0;
if (d == 1) return 1;
if (m[d].count(target)) return m[d][target];
return m[d][target] = (((long)dfs(d, target - 1) + dfs(d - 1, target - 1)) % mod - dfs(d - 1, target - f - 1) + mod) % mod;
}
public:
int numRollsToTarget(int d, int f, int target) {
m.assign(d + 1, {});
this->f = f;
return dfs(d, target);
}
};


Using array is always more time efficient.

// OJ: https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/
// Time: O(DT)
// Space: O(DT)
class Solution {
int m[31][1001] = {};
long mod = 1e9+7, f;
int dfs(int d, int target) {
if (target < d || target > d * f) return 0;
if (d == 1) return 1;
if (m[d][target] != -1) return m[d][target];
return m[d][target] = (((long)dfs(d, target - 1) + dfs(d - 1, target - 1)) % mod - dfs(d - 1, target - f - 1) + mod) % mod;
}
public:
int numRollsToTarget(int d, int f, int target) {
memset(m, -1, sizeof(m));
this->f = f;
return dfs(d, target);
}
};


## Solution 3. DP Bottom-up

// OJ: https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/
// Time: O(DTF)
// Space: O(DT)
class Solution {
public:
int numRollsToTarget(int d, int f, int target) {
long dp[31][1001] = {}, mod = 1e9+7;
for (int j = 1; j <= f; ++j) dp[1][j] = 1;
for (int i = 2; i <= d; ++i) {
for (int t = i; t <= target && t <= i * f; ++t) {
for (int j = 1; j <= f && j < t; ++j) {
dp[i][t] = (dp[i][t] + dp[i - 1][t - j]) % mod;
}
}
}
return dp[d][target];
}
};


## Solution 4. DP Bottom-up with Optimization

// OJ: https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/
// Time: O(DT)
// Space: O(DT)
class Solution {
public:
int numRollsToTarget(int d, int f, int target) {
long dp[31][1001] = {}, mod = 1e9+7;
for (int j = 1; j <= f; ++j) dp[1][j] = 1;
for (int i = 2; i <= d; ++i) {
for (int t = i; t <= target && t <= i * f; ++t) {
dp[i][t] = (dp[i][t - 1] + dp[i - 1][t - 1]) % mod;
if (t - f - 1 > 0) dp[i][t] = (dp[i][t] - dp[i - 1][t - f - 1] + mod) % mod;
}
}
return dp[d][target];
}
};

• class Solution {
public int numRollsToTarget(int d, int f, int target) {
int min = d, max = d * f;
if (target < min || target > max)
return 0;
if (d == 1 || target == min || target == max)
return 1;
final int MODULO = 1000000007;
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 1; i <= d; i++) {
for (int j = target; j >= 0; j--) {
dp[j] = 0;
int upper = Math.min(f, j);
for (int k = 1; k <= upper; k++)
dp[j] = (dp[j] + dp[j - k]) % MODULO;
}
}
return dp[target];
}
}

############

class Solution {
private static final int MOD = (int) 1e9 + 7;

public int numRollsToTarget(int n, int k, int target) {
int[][] f = new int[n + 1][target + 1];
f[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= Math.min(target, i * k); ++j) {
for (int h = 1; h <= Math.min(j, k); ++h) {
f[i][j] = (f[i][j] + f[i - 1][j - h]) % MOD;
}
}
}
return f[n][target];
}
}

• // OJ: https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/
// Time: O(DFT)
// Space: O(DT)
class Solution {
vector<unordered_map<int, int>> m;
long mod = 1e9+7;
int dfs(int d, int f, int target) {
if (target < d || target > d * f) return 0;
if (d == 1) return 1;
if (m[d].count(target)) return m[d][target];
long cnt = 0;
for (int j = 1; j <= f && j <= target; ++j) {
int c = dfs(d - 1, f, target - j);
cnt = (cnt + c) % mod;
}
return m[d][target] = cnt;
}
public:
int numRollsToTarget(int d, int f, int target) {
m.assign(d + 1, {});
return dfs(d, f, target);
}
};

• class Solution:
def numRollsToTarget(self, n: int, k: int, target: int) -> int:
f = [[0] * (target + 1) for _ in range(n + 1)]
f[0][0] = 1
mod = 10**9 + 7
for i in range(1, n + 1):
for j in range(1, min(i * k, target) + 1):
for h in range(1, min(j, k) + 1):
f[i][j] = (f[i][j] + f[i - 1][j - h]) % mod
return f[n][target]

############

# 1155. Number of Dice Rolls With Target Sum
# https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/

class Solution:
def numRollsToTarget(self, d: int, f: int, target: int) -> int:
M = 10 ** 9 + 7

@cache
def dp(d, target):
if d == 0: return 1 if target == 0 else 0

count = 0
for k in range(max(0, target - f), target):
count += dp(d - 1, k)

return count

return dp(d, target) % M


• func numRollsToTarget(n int, k int, target int) int {
const mod int = 1e9 + 7
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, target+1)
}
f[0][0] = 1
for i := 1; i <= n; i++ {
for j := 1; j <= min(target, i*k); j++ {
for h := 1; h <= min(j, k); h++ {
f[i][j] = (f[i][j] + f[i-1][j-h]) % mod
}
}
}
return f[n][target]
}

func min(a, b int) int {
if a < b {
return a
}
return b
}