# 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.