Mid/SeniorDynamic Programming
Number of Dice Rolls With Target Sum
You have n dice, and each dice has k faces numbered from 1 to k.
Given three integers n, k, and target, return the number of possible ways, out of the k^n total ways, to roll the dice so that the sum of the face-up numbers equals target.
Since the answer may be too large, return it modulo 10^9 + 7.
Example 1
Input
n = 1, k = 6, target = 3Output
1You throw one die with 6 faces, and there is only one way to get a sum of 3.
Example 2
Input
n = 2, k = 6, target = 7Output
6There are 6 ways to get a sum of 7: 1+6, 2+5, 3+4, 4+3, 5+2, and 6+1.
Constraints
- 1 <= n, k <= 30
- 1 <= target <= 1000