https://leetcode.com/problems/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 <= 301 <= target <= 1000
This problem is like 518. Coin Change 2, with the difference that the total number of coins (dices) should be equal to
d.Basic Solution (TLE)
A basic brute-force solution could be to try all combinations of all faces for all dices, and count the ones that give a total sum of
target.int numRollsToTarget(int d, int f, int target, int res = 0) {
if (d == 0 || target <= 0) return d == target;
for (auto i = 1; i <= f; ++i)
res = (res + numRollsToTarget(d - 1, f, target - i)) % 1000000007;
return res;
}
d == targetis the shorthand ford == 0 && target == 0.
Complexity Analysis
Runtime: O(f ^ d).
Memory: O(d) for the stack.
Memory: O(d) for the stack.
Top-down DP
We memoise the previously computed results for dice
i and and target.
Since
dp is initialized with zeros, we store there res + 1 to check if the result has been pre-computed. This is an optimization for brevity and speed.int dp[31][1001] = {};
int numRollsToTarget(int d, int f, int target, int res = 0) {
if (d == 0 || target <= 0) return d == target;
if (dp[d][target]) return dp[d][target] - 1;
for (auto i = 1; i <= f; ++i)
res = (res + numRollsToTarget(d - 1, f, target - i)) % 1000000007;
dp[d][target] = res + 1;
return res;
}
Complexity Analysis
Runtime: O(d * f * target).
Memory: O(d * target) for the memoisation.
Memory: O(d * target) for the memoisation.
Bottom-Up DP
We can define our
dp[i][k] as number of ways we can get k using i dices. As an initial point, there is one way to get to 0 using zero dices.
Then, for each dice
i and face j, accumulate the number of ways we can get to k.
Note that for the bottom-up solution, we can reduce our memory complexity as we only need to store counts for the previous dice.
int numRollsToTarget(int d, int f, int target) {
vector<int> dp(target + 1);
dp[0] = 1;
for (int i = 1; i <= d; ++i) {
vector<int> dp1(target + 1);
for (int j = 1; j <= f; ++j)
for (auto k = j; k <= target; ++k)
dp1[k] = (dp1[k] + dp[k - j]) % 1000000007;
swap(dp, dp1);
}
return dp[target];
}
Complexity Analysis
Runtime: O(d * f * target).
Memory: O(target) as we only store counts for the last dice.
Memory: O(target) as we only store counts for the last dice.
Further Optimizations
We can re-use the same array if we process our targets backwards. Just be sure to clear the previous target count (
dp[k]) - this value is for the previous dice and we do not need it anymore.Note that we need to flip the order of processing - we iterate though targets first (k), and then through the faces (j). I left the variable names the same as for the previous solution.
Thanks dylan20 for this memory optimization tip!
You can also see that, this way, we can stop at
dp[target] when processing the last dice.int numRollsToTarget(int d, int f, int target) {
int dp[target + 1] = { 1 }, i, j, k;
for (i = 1; i <= d; ++i)
for (k = target; k >= (i == d ? target : 0); --k)
for (j = k - 1, dp[k] = 0; j >= max(0, k - f); --j)
dp[k] = (dp[k] + dp[j]) % 1000000007;
return dp[target];
} int MOD = 1000000000 + 7;
Map<String, Integer> memo = new HashMap<>();
public int numRollsToTarget(int d, int f, int target) {
if (d == 0 && target == 0) {
return 1;
}
if (d == 0 || target == 0) {
return 0;
}
String str = d + " " + target;
if (memo.containsKey(str)) {
return memo.get(str);
}
int res = 0;
for (int i = 1; i <= f; i++) {
if (target >= i) {
res = (res + numRollsToTarget(d - 1, f, target - i)) % MOD;
} else {
break;
}
}
memo.put(str, res);
return res;
} public int numRollsToTarget(int d, int f, int target) {
int MOD = 1000000007;
int[][] dp = new int[d + 1][target + 1];
dp[0][0] = 1;
//how many possibility 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 { //watch out below condition, or NPE
for(int k = 1; k <= f && k <= j ; k++) {
dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD;
}
}
}
}
return dp[d][target];
}动态规划)
- 设 表示掷了前 i 个骰子，得到总和为 j 的方案数。
- 初始时，，表示没有掷骰子时，得到 0 的方案数为 1。其余方案数均为 0。
- 转移时，枚举这一次掷的骰子的点数。然后，转移 ，其中 ，且 。
- 最后答案为 。
时间复杂度
- 总共有 个状态，每次转移需要 的时间，故总时间复杂度为 。
空间复杂度
- 和状态数量一致，故空间复杂度为 。
int numRollsToTarget(int d, int f, int target) {
const int mod = 1000000007;
vector<vector<int>> dp(d + 1, vector<int>(target + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= d; i++)
for (int j = 1; j <= f; j++)
for (int k = j; k <= target; k++)
dp[i][k] = (dp[i][k] + dp[i - 1][k - j]) % mod;
return dp[d][target];
}
首先看下 dp[i][t] 表示什么，这里表示使用前 i 个色子能够拼出 t 数字的最多形式个数。
- 初始化
- dp[0][0] = 1
- 状态转移
- 掷骰子一次有 f 种可能
- 只存两行降维
- 滚动数组降维
https://blog.xiadong.info/2019/08/11/LeetCode-1155-Number-of-Dice-Rolls-With-Target-Sum/
基本思路是使用动态规划，有
n个骰子投出m点的可能数量为sum(n-1个骰子投出m-1的数量, n-1个骰子投出m-2的数量,..., n-1个骰子投出m-f的数量)。对于每一个d都要遍历一遍f个点，每一次遍历中要再遍历一次d-1时的f个点所以最佳时间复杂度应为O(df^2)，在我的实现中因为不知道d-1时的可能点数的起始位置所以实际遍历了所有d*f个可能，实际复杂度为O(d^2f^2)。