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 <= 301 <= 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 }