## Similar Problems

Similar Problems not available

# Number Of Dice Rolls With Target Sum - Leetcode Solution

LeetCode: Number Of Dice Rolls With Target Sum Leetcode Solution

Difficulty: Medium

Topics: dynamic-programming

The problem statement reads:

You have `d`

dice and each die has `f`

faces numbered `1`

to `f`

. You are given a target sum `target`

. You have to find the number of possible ways to roll the dice to get the target sum.

The brute-force approach to solve this problem is to generate all possible combinations of throwing the `d`

dice with their respective `f`

faces and add up the ones whose sum equals `target`

. However, given the constraints of the problem (1 ≤ d, f ≤ 30, 1 ≤ target ≤ 1000), this approach will take a long time to execute.

A better approach to solve this problem is Dynamic Programming (DP). We will create a 2D array `dp[][]`

of dimensions `(d+1) x (target+1)`

where `dp[i][j]`

will represent the number of ways to achieve the target sum `j`

using `i`

dice.

For the base cases, we initialize `dp[0][0]`

to `1`

(since no dice are required to throw and the sum is already zero) and initialize the rest of `dp[0][j]`

as `0`

(since no dice are thrown, no sum can be achieved). Similarly, we initialize `dp[i][0]`

as `0`

(since with `i`

dice, the sum can never be zero).

The recurrence relation to compute `dp[i][j]`

will be as follows. For each die `k`

(`k`

ranges from `1`

to `f`

) thrown by the current player, we add to the sum `k`

and check how many ways we can achieve the remaining sum of `j - k`

. The number of ways to achieve the remaining sum will be `dp[i-1][j-k]`

. We sum over all possible dice values to compute `dp[i][j]`

.

Therefore, the recurrence relation will be as follows:

`dp[i][j] = dp[i][j] + dp[i-1][j-k]`

for all `k`

such that `1 ≤ k ≤ f`

and `j-k ≥ 0`

.

The final answer will be the value of `dp[d][target]`

.

The time complexity of this approach is O(d x f x target) and the space complexity is O(d x target).

Code:

```
class Solution {
public:
int numRollsToTarget(int d, int f, int target) {
int dp[d+1][target+1]; // dp[i][j] represents the number of ways to achieve target j using i die
memset(dp, 0, sizeof(dp));
dp[0][0] = 1; // Base case
for(int i = 1; i <= d; i++) {
for(int j = 1; j <= target; j++) {
for(int k = 1; k <= f; k++) {
if(j - k >= 0) {
dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % 1000000007;
}
}
}
}
return dp[d][target];
}
};
```

Reference: Number of Dice Rolls With Target Sum

## Number Of Dice Rolls With Target Sum Solution Code

`1`