#1155
Number of Dice Rolls With Target Sum
specialist · 675 · lc medium +30 · verified · 62.2% accepted · 5,322 likes · top 63%
Description
You have n dice, each having k faces labeled 1 through k.
Given integers n, k, and target, determine how many of the kn possible roll outcomes produce face values that sum exactly to target. Since the result can be very 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.
Code
1
2
3