# 1155. 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 109 + 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`

`dp[i][k] = (dp[i][k] + dp[i - 1][k - j]) % M;`

``````class Solution {
public:
int numRollsToTarget(int d, int f, int target) {
int M = 1e9 + 7;
vector<vector<int>> dp(d + 1, vector<int>(target + 1));
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]) % M;
}
}
}
return dp[d][target];
}
};
``````

``````class Solution {
public:
int numRollsToTarget(int d, int f, int target) {
int M = 1e9 + 7;
vector<int> dp(target + 1);
dp[0] = 1;
for (int i = 1; i <= d; ++i) {
vector<int> t(target + 1);
for (int j = 1; j <= f; ++j) {
for (int k = j; k <= target; ++k) {
t[k] = (t[k] + dp[k - j]) % M;
}
}
swap(dp, t);
}
return dp[target];
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1155

Coin Change 2

Equal Sum Arrays With Minimum Number of Operations

https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/

https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/discuss/355841/Java-Memo-DFS

https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/discuss/355940/C%2B%2B-Coin-Change-2

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation