1155. Number of Dice Rolls With Target Sum
You have n
dice and each die has k
faces numbered from 1
to k
.
Given three integers n
, k
, and target
, return the number of possible ways (out of the kn
total ways) to roll the dice so the sum of the face-up numbers equals target
. Since the answer may be too 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.
Constraints:
1 <= n, k <= 30
1 <= target <= 1000
Solution:
By reading the question, you would know this is a simple DP question. What we need to figure out here is the DP state that is what we need to store in our DP array.
We will make a 2D DP of n*target size which will store the number of dice rolls remaining and the target remaining or vice versa.
Here is the code for the DP Solution:
Another way of doing the same thing is that instead of making a 2D array we will make a 1D array of size target+1 and we will run a for loop from 1 to n.
Inside the for loop, we will go from 1 to K and in a temp array, we will store the current our result for the target. Why are we doing this? If we make a 2D array it will take more space.
At last, we will change our DP with the temp array.
At last, we will change our DP with the temp array.
Here is the code for better understanding.
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.