1155. Number of Dice Rolls With Target Sum | LeetCode DP Solution

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.

Here is the code for better understanding.