# Number of Dice Rolls With Target Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-dice-rolls-with-target-sum)
Canonical: https://scaleengineer.com/dsa/problems/number-of-dice-rolls-with-target-sum
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Companies:** [StackAdapt](https://scaleengineer.com/companies/stackadapt)
---
## Problem
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_ `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`

# Approaches
## Brute-Force Recursion
The most intuitive approach is to simulate all possible outcomes of rolling `n` dice. We can use a recursive function to explore every combination. The function's state can be defined by the number of dice remaining to be rolled and the remaining target sum.
**Time:** O(k^n) - The recursion tree has a depth of `n`, and each function call branches `k` times. This leads to an exponential number of calls, making it infeasible for the given constraints. · **Space:** O(n) - The space is dominated by the maximum depth of the recursion stack, which is equal to the number of dice `n`.
**Pros:** Simple to understand and implement.; Correctly models the problem's logic.
**Cons:** Extremely inefficient due to exponential time complexity.; Will result in a 'Time Limit Exceeded' error for most constraints beyond the smallest examples.
### Explanation
We define a recursive function, say `solve(d, t)`, which calculates the number of ways to get a sum `t` using `d` dice. The base case for the recursion is when we have no dice left (`d == 0`). If the target sum is also zero (`t == 0`), we have found one valid way. Otherwise, it's an invalid path. In the recursive step, for the current die, we iterate through all possible face values from 1 to `k`. For each face value `f`, we make a recursive call with one less die and a reduced target sum: `solve(d - 1, t - f)`. The total number of ways is the sum of the results from these recursive calls. The initial call to the function would be `solve(n, target)`. This method explores the entire search space, which grows exponentially.

```java
class Solution {
    private static final int MOD = 1_000_000_007;

    public int numRollsToTarget(int n, int k, int target) {
        // Early exit for impossible targets
        if (target < n || target > n * k) {
            return 0;
        }
        return solve(n, k, target);
    }

    private int solve(int n, int k, int remainingTarget) {
        // Base case: If we have used all dice
        if (n == 0) {
            // If the target is also 0, we found a valid combination
            return remainingTarget == 0 ? 1 : 0;
        }

        // If remaining target is impossible to achieve with remaining dice
        if (remainingTarget <= 0) {
            return 0;
        }

        int ways = 0;
        // Try each possible face for the current die
        for (int face = 1; face <= k; face++) {
            // Recur for the next die with the reduced target
            ways = (ways + solve(n - 1, k, remainingTarget - face)) % MOD;
        }
        return ways;
    }
}
```
### Algorithm
- Define a recursive function `solve(d, t)` that returns the number of ways to get sum `t` with `d` dice.
- **Base Case 1:** If `d == 0` and `t == 0`, a valid combination is found. Return 1.
- **Base Case 2:** If `d == 0` or `t <= 0`, it's an impossible path. Return 0.
- **Recursive Step:** Iterate through each possible face value `f` from 1 to `k`. For each `f`, make a recursive call `solve(d - 1, t - f)`.
- Sum up the results from all recursive calls, taking the modulo at each step.
- The initial call is `solve(n, target)`.

## Top-Down Dynamic Programming (Memoization)
The brute-force approach suffers from re-calculating the same subproblems (e.g., ways to get sum `t` with `d` dice) repeatedly. We can significantly optimize this by using memoization, a top-down dynamic programming technique. We store the results of each subproblem `(d, t)` in a cache (or memoization table) and reuse them when needed.
**Time:** O(n * target * k) - There are `n * target` unique states for `(d, t)`. Each state's computation involves a loop of size `k`. · **Space:** O(n * target) - For the memoization table. The recursion stack also uses O(n) space, but this is dominated by the table size.
**Pros:** Drastically reduces time complexity from exponential to polynomial.; Guaranteed to pass within the given time limits.; Maintains the logical structure of the recursive solution.
**Cons:** Requires O(n * target) space, which can be large for the maximum constraints.
### Explanation
We enhance the recursive solution by adding a 2D array, `memo[d][t]`, to store the result of `solve(d, t)`. The dimensions of this table will be `(n+1) x (target+1)`. Before any computation within the recursive function, we check if the result for the current state `(d, t)` is already in our `memo` table. If it is, we return the stored value immediately, avoiding redundant computation. If the result is not in the table, we compute it as in the brute-force approach. After computing the result, we store it in `memo[d][t]` before returning. This ensures that each unique subproblem is solved only once.

```java
class Solution {
    private static final int MOD = 1_000_000_007;
    private Integer[][] memo;

    public int numRollsToTarget(int n, int k, int target) {
        if (target < n || target > n * k) {
            return 0;
        }
        memo = new Integer[n + 1][target + 1];
        return solve(n, k, target);
    }

    private int solve(int n, int k, int remainingTarget) {
        if (n == 0) {
            return remainingTarget == 0 ? 1 : 0;
        }
        if (remainingTarget <= 0) {
            return 0;
        }
        if (memo[n][remainingTarget] != null) {
            return memo[n][remainingTarget];
        }

        int ways = 0;
        for (int face = 1; face <= k; face++) {
            if (remainingTarget - face >= 0) {
                 ways = (ways + solve(n - 1, k, remainingTarget - face)) % MOD;
            }
        }
        
        return memo[n][remainingTarget] = ways;
    }
}
```
### Algorithm
- Create a 2D array `memo[n+1][target+1]` to store the results of subproblems, initialized to a sentinel value (e.g., `null` or -1).
- Use the same recursive structure as the brute-force approach.
- Before computing `solve(d, t)`, check if `memo[d][t]` has already been computed. If so, return the stored value.
- If not, compute the result by iterating from `f = 1` to `k` and summing up `solve(d-1, t-f)`.
- Store the computed result in `memo[d][t]` before returning it.

## Bottom-Up Dynamic Programming
Instead of a top-down recursive approach, we can solve the problem iteratively using bottom-up dynamic programming. This approach builds the solution from the smallest subproblems up to the final problem. It often has slightly better performance in practice by avoiding recursion overhead.
**Time:** O(n * target * k) - We have three nested loops for the number of dice, the target sum, and the face values. · **Space:** O(n * target) - For the 2D DP table.
**Pros:** Avoids recursion overhead, which can lead to a small performance gain.; Conceptually clear and systematic.
**Cons:** Has the same asymptotic time and space complexity as the memoized approach.; The three nested loops can be inefficient if `k` is large.
### Explanation
We define a 2D DP table, `dp[i][j]`, to store the number of ways to achieve a sum `j` using `i` dice. The table size is `(n+1) x (target+1)`. The base case is `dp[0][0] = 1`, representing one way to get a sum of 0 with 0 dice (the empty roll). We then iterate from `i = 1` to `n` (number of dice) and for each `i`, we iterate from `j = 1` to `target` (the sum). The state transition formula is derived from the idea that the number of ways to get sum `j` with `i` dice is the sum of ways to get `j-f` with `i-1` dice, where `f` is the outcome of the `i`-th die. This gives the recurrence: `dp[i][j] = sum(dp[i-1][j-f])` for `f` from 1 to `k`. The final answer is the value at `dp[n][target]`.

```java
class Solution {
    public int numRollsToTarget(int n, int k, int target) {
        final int MOD = 1_000_000_007;
        int[][] dp = new int[n + 1][target + 1];
        
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) { // i = number of dice
            for (int j = 1; j <= target; j++) { // j = current sum
                for (int face = 1; face <= k; face++) { // face = value of the current die
                    if (j - face >= 0) {
                        dp[i][j] = (dp[i][j] + dp[i-1][j - face]) % MOD;
                    }
                }
            }
        }
        return dp[n][target];
    }
}
```
### Algorithm
- Create a 2D DP table `dp[n+1][target+1]`.
- Initialize `dp[0][0] = 1`, as there's one way to get a sum of 0 with 0 dice.
- Iterate through the number of dice `i` from 1 to `n`.
- For each `i`, iterate through the target sum `j` from 1 to `target`.
- For each `(i, j)`, iterate through the possible face values `f` from 1 to `k`.
- The transition is `dp[i][j] = (dp[i][j] + dp[i-1][j-f]) % MOD` for `j >= f`.
- The final answer is `dp[n][target]`.

## Optimized Bottom-Up DP with Sliding Window
The inner loop over `k` faces in the previous DP approach can be optimized. The calculation `dp[i][j] = dp[i-1][j-1] + ... + dp[i-1][j-k]` is a sum over a sliding window of size `k` on the previous row `dp[i-1]`. We can calculate this sum in O(1) time by reusing the sum calculated for `dp[i][j-1]`.
**Time:** O(n * target) - We have eliminated the O(k) loop, resulting in a much faster solution. · **Space:** O(n * target) - The space complexity remains the same as we still use the 2D DP table.
**Pros:** Significantly improved time complexity, making it much faster.; Efficient for all constraints.
**Cons:** Still requires O(n * target) space.
### Explanation
The recurrence `dp[i][j] = sum_{f=1 to k} dp[i-1][j-f]` can be rewritten to eliminate the inner loop. By observing the relationship between `dp[i][j]` and `dp[i][j-1]`, we can derive a new recurrence: `dp[i][j] = dp[i][j-1] + dp[i-1][j-1] - dp[i-1][j-k-1]`. This allows us to compute `dp[i][j]` in O(1) time using previously computed values. `dp[i][j-1]` is the sum for the previous target, `dp[i-1][j-1]` is the new value entering the sliding window, and `dp[i-1][j-k-1]` is the value leaving the window. This optimization reduces the time complexity by a factor of `k`.

```java
class Solution {
    public int numRollsToTarget(int n, int k, int target) {
        final int MOD = 1_000_000_007;
        int[][] dp = new int[n + 1][target + 1];
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) { // number of dice
            long windowSum = 0;
            for (int j = 1; j <= target; j++) { // current sum
                windowSum = (windowSum + dp[i-1][j-1]) % MOD;
                if (j - k - 1 >= 0) {
                    windowSum = (windowSum - dp[i-1][j-k-1] + MOD) % MOD;
                }
                dp[i][j] = (int)windowSum;
            }
        }
        return dp[n][target];
    }
}
```
### Algorithm
- Create a 2D DP table `dp[n+1][target+1]` and set `dp[0][0] = 1`.
- Iterate `i` from 1 to `n` (dice) and `j` from 1 to `target` (sum).
- Instead of a third loop, use the recurrence: `dp[i][j] = dp[i][j-1] + dp[i-1][j-1] - dp[i-1][j-k-1]`.
- This calculates the sum of `dp[i-1][j-f]` over `f` in O(1) time.
- `dp[i][j-1]` represents the previous window sum.
- `dp[i-1][j-1]` is the new element entering the window.
- `dp[i-1][j-k-1]` is the element leaving the window.
- Handle modulo arithmetic carefully, especially with subtraction.
- The answer is `dp[n][target]`.

## Space-Optimized Bottom-Up DP with Sliding Window
This is the most efficient approach, combining the time optimization from the sliding window technique with space optimization. Since the calculation for the `i`-th row of our DP table only depends on the `(i-1)`-th row, we don't need to store all `n` rows. We only need to keep track of the previous row's results to compute the current row, reducing space complexity significantly.
**Time:** O(n * target) - The time complexity is the same as the previous optimized approach, which is optimal. · **Space:** O(target) - We only need space proportional to the target sum for two 1D arrays, which is a significant improvement.
**Pros:** Optimal time complexity of O(n * target).; Optimal space complexity of O(target).; Most efficient solution for this problem.
**Cons:** The logic can be slightly more complex to grasp initially compared to the more straightforward DP approaches.
### Explanation
We can optimize the space of the sliding window DP approach. Instead of a 2D table, we use two 1D arrays: `dp` (representing the results for `i-1` dice) and `newDp` (for the current `i` dice), both of size `target+1`. We iterate from `i = 1` to `n`. In each iteration, we compute `newDp` based on `dp`. To compute `newDp[j]`, we maintain a `windowSum` of the last `k` values from the `dp` array. As we iterate `j` from 1 to `target`, we update the `windowSum` by adding the new element `dp[j-1]` and removing the old element `dp[j-k-1]` (if the window is full). `newDp[j]` is then set to this `windowSum`. After computing the `newDp` array for the current number of dice, we replace `dp` with `newDp` for the next iteration. The final answer is `dp[target]` after `n` iterations.

```java
class Solution {
    public int numRollsToTarget(int n, int k, int target) {
        final int MOD = 1_000_000_007;
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int i = 1; i <= n; i++) { // number of dice
            int[] newDp = new int[target + 1];
            int windowSum = 0;
            for (int j = 1; j <= target; j++) { // current sum
                // Add dp[j-1] from previous iteration (i-1) to window
                windowSum = (windowSum + dp[j - 1]) % MOD;
                // Remove dp[j-k-1] from previous iteration if window is full
                if (j > k) {
                    windowSum = (windowSum - dp[j - k - 1] + MOD) % MOD;
                }
                newDp[j] = windowSum;
            }
            dp = newDp;
        }
        return dp[target];
    }
}
```
### Algorithm
- Use two 1D arrays, `dp` (for `i-1` dice) and `newDp` (for `i` dice), of size `target+1`.
- Initialize `dp[0] = 1`.
- Loop `i` from 1 to `n`.
- Inside, create `newDp` and a `windowSum` variable initialized to 0.
- Loop `j` from 1 to `target`.
- Update `windowSum` by adding `dp[j-1]` and subtracting `dp[j-k-1]` (if `j > k`).
- Set `newDp[j] = windowSum`.
- After the inner loop, update `dp = newDp`.
- After `n` iterations, the answer is `dp[target]`.

# Solutions
### Java

```java
class Solution {
public
  int numRollsToTarget(int n, int k, int target) {
    final int mod = (int)1 e9 + 7;
    int[][] f = new int[n + 1][target + 1];
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= Math.min(target, i * k); ++j) {
        for (int h = 1; h <= Math.min(j, k); ++h) {
          f[i][j] = (f[i][j] + f[i - 1][j - h]) % mod;
        }
      }
    }
    return f[n][target];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numRollsToTarget(int n, int k, int target) {
    const int mod = 1e9 + 7;
    int f[n + 1][target + 1];
    memset(f, 0, sizeof f);
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= min(target, i * k); ++j) {
        for (int h = 1; h <= min(j, k); ++h) {
          f[i][j] = (f[i][j] + f[i - 1][j - h]) % mod;
        }
      }
    }
    return f[n][target];
  }
};

```

### Python

```python
class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int: f = [[0] * (target + 1) for _ in range(n + 1)] f[0][0] = 1 mod = 10 ** 9 + 7 for i in range(1, n + 1): for j in range(1, min(i * k, target) + 1): for h in range(1, min(j, k) + 1): f[i][j] = (f[i][j] + f[i - 1][j - h]) % mod return f[n][target]

```