# Dice Roll Simulation
**Difficulty:** HARD
[External](https://leetcode.com/problems/dice-roll-simulation)
Canonical: https://scaleengineer.com/dsa/problems/dice-roll-simulation
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Akuna Capital](https://scaleengineer.com/companies/akuna-capital)
---
## Problem
A die simulator generates a random number from `1` to `6` for each roll. You introduced a constraint to the generator such that it cannot roll the number `i` more than `rollMax[i]` (**1-indexed**) consecutive times.

Given an array of integers `rollMax` and an integer `n`, return _the number of distinct sequences that can be obtained with exact_ `n` _rolls_. Since the answer may be too large, return it **modulo** `109 + 7`.

Two sequences are considered different if at least one element differs from each other.

**Example 1:**

**Input:** n = 2, rollMax = [1,1,2,2,2,3]
**Output:** 34
**Explanation:** There will be 2 rolls of die, if there are no constraints on the die, there are 6 * 6 = 36 possible combinations. In this case, looking at rollMax array, the numbers 1 and 2 appear at most once consecutively, therefore sequences (1,1) and (2,2) cannot occur, so the final answer is 36-2 = 34.

**Example 2:**

**Input:** n = 2, rollMax = [1,1,1,1,1,1]
**Output:** 30

**Example 3:**

**Input:** n = 3, rollMax = [1,1,1,2,2,3]
**Output:** 181

**Constraints:**

* `1 <= n <= 5000`
* `rollMax.length == 6`
* `1 <= rollMax[i] <= 15`

# Approaches
## 3D Dynamic Programming
This approach uses a three-dimensional dynamic programming table to solve the problem. The state `dp[i][j][k]` represents the number of valid sequences of length `i` that end with exactly `k` consecutive rolls of the number `j+1`. We build this table up from `i=1` to `n`, calculating the number of possibilities at each step based on the results of the previous step.
**Time:** O(n * faces * max_rollMax). The loops iterate up to `n`, 6 (faces), and `max_rollMax` (at most 15). · **Space:** O(n * faces * max_rollMax). We use a 3D array of size `(n+1) x 6 x 16`.
**Pros:** Conceptually straightforward application of dynamic programming.; Easy to understand the state transitions.
**Cons:** High space complexity, which can be an issue for larger `n`.; The time complexity is higher than more optimized approaches.
### Explanation
In this method, we define a DP state `dp[i][j][k]` as the number of distinct sequences of length `i` rolls, where the last roll is face `j` (0-indexed), and it's the `k`-th consecutive occurrence of `j`.

The state transitions are as follows:
*   To form a sequence of length `i` ending with `k > 1` consecutive `j`'s, we must append a `j` to a sequence of length `i-1` that ended with `k-1` consecutive `j`'s. Thus, `dp[i][j][k] = dp[i-1][j][k-1]`.
*   To form a sequence of length `i` ending with `k = 1` consecutive `j`'s, we must append a `j` to a sequence of length `i-1` that ended with any face other than `j`. The number of such sequences is the total number of valid sequences of length `i-1` minus the number of sequences of length `i-1` ending in `j`.

We can optimize the calculation for the `k=1` case by pre-calculating the total number of sequences for length `i-1`. The final answer is the sum of `dp[n][j][k]` over all possible `j` and `k`.

```java
class Solution {
    public int dieSimulator(int n, int[] rollMax) {
        long MOD = 1_000_000_007;
        // dp[i][j][k]: number of sequences of length i ending with k consecutive j's
        long[][][] dp = new long[n + 1][6][16];
        long[] total = new long[n + 1];

        // Base case: i = 1
        for (int j = 0; j < 6; j++) {
            dp[1][j][1] = 1;
        }
        total[1] = 6;

        for (int i = 2; i <= n; i++) {
            long currentTotal = 0;
            for (int j = 0; j < 6; j++) { // current face
                long sumEndingWithJPrev = 0;
                for (int k = 1; k <= rollMax[j]; k++) {
                    sumEndingWithJPrev = (sumEndingWithJPrev + dp[i - 1][j][k]) % MOD;
                }

                // Case 1: current roll j is the first in a consecutive sequence
                dp[i][j][1] = (total[i - 1] - sumEndingWithJPrev + MOD) % MOD;

                // Case 2: current roll j extends a consecutive sequence
                for (int k = 2; k <= rollMax[j]; k++) {
                    dp[i][j][k] = dp[i - 1][j][k - 1];
                }
                
                long sumEndingWithJCurr = 0;
                for (int k = 1; k <= rollMax[j]; k++) {
                    sumEndingWithJCurr = (sumEndingWithJCurr + dp[i][j][k]) % MOD;
                }
                currentTotal = (currentTotal + sumEndingWithJCurr) % MOD;
            }
            total[i] = currentTotal;
        }

        return (int) total[n];
    }
}
```
### Algorithm
*   Define a 3D DP state `dp[i][j][k]` as the number of distinct sequences of length `i` rolls, where the last roll is face `j` (0-indexed), and it's the `k`-th consecutive occurrence of `j`.
*   Initialize a 3D array `dp[n+1][6][16]` to store these values.
*   **Base Case:** For `i = 1`, we can roll any face `j` once. So, `dp[1][j][1] = 1` for all `j` from 0 to 5.
*   **Transitions:** Iterate from `i = 2` to `n`. For each face `j`:
    *   To form a sequence ending with `k > 1` consecutive `j`'s, we must append a `j` to a sequence of length `i-1` that ended with `k-1` consecutive `j`'s. Thus, `dp[i][j][k] = dp[i-1][j][k-1]`.
    *   To form a sequence ending with `k = 1` consecutive `j`'s, we must append a `j` to any valid sequence of length `i-1` that ended with a face other than `j`. This can be calculated as `total_sequences[i-1] - sequences_ending_with_j[i-1]`.
*   To optimize, we maintain an array `total[i]` storing the total number of valid sequences of length `i`.
*   The final answer is the sum of `dp[n][j][k]` over all possible `j` and `k`, which is `total[n]`.

## Space-Optimized 3D Dynamic Programming
This approach improves upon the 3D DP solution by reducing its space complexity. Since the calculation for `dp[i]` only depends on the results from `dp[i-1]`, we don't need to store the entire DP table. We can use only two layers of the DP table: one for the current state `i` and one for the previous state `i-1`, effectively reducing the space complexity from linear to constant with respect to `n`.
**Time:** O(n * faces * max_rollMax). The time complexity remains the same as the previous approach. · **Space:** O(faces * max_rollMax). The space is now constant with respect to `n`, which is a significant improvement.
**Pros:** Greatly reduced space complexity compared to the basic 3D DP.; Makes the solution feasible for much larger `n` if memory were the only constraint.
**Cons:** Time complexity is still not optimal.; Involves managing two tables and copying data between them in each iteration.
### Explanation
The core logic remains the same as the basic 3D DP approach. The key difference is memory management. We observe that to compute the number of sequences for `i` rolls, we only need the results from `i-1` rolls. Therefore, storing the entire history for `1...i-2` is unnecessary.

We use two 2D arrays, `prev_dp` to hold the results for `i-1` rolls and `dp` to compute the results for `i` rolls. After each iteration `i`, the contents of `dp` become the `prev_dp` for the next iteration `i+1`.

```java
class Solution {
    public int dieSimulator(int n, int[] rollMax) {
        long MOD = 1_000_000_007;
        long[][] prev_dp = new long[6][16];
        long total_prev = 0;

        // Base case: i = 1
        for (int j = 0; j < 6; j++) {
            prev_dp[j][1] = 1;
        }
        total_prev = 6;
        
        if (n == 1) return (int) total_prev;

        for (int i = 2; i <= n; i++) {
            long[][] dp = new long[6][16];
            long total_curr = 0;
            for (int j = 0; j < 6; j++) {
                long sumEndingWithJPrev = 0;
                for (int k = 1; k <= rollMax[j]; k++) {
                    sumEndingWithJPrev = (sumEndingWithJPrev + prev_dp[j][k]) % MOD;
                }

                dp[j][1] = (total_prev - sumEndingWithJPrev + MOD) % MOD;

                for (int k = 2; k <= rollMax[j]; k++) {
                    dp[j][k] = prev_dp[j][k - 1];
                }
                
                long sumEndingWithJCurr = 0;
                for (int k = 1; k <= rollMax[j]; k++) {
                    sumEndingWithJCurr = (sumEndingWithJCurr + dp[j][k]) % MOD;
                }
                total_curr = (total_curr + sumEndingWithJCurr) % MOD;
            }
            prev_dp = dp;
            total_prev = total_curr;
        }

        return (int) total_prev;
    }
}
```
### Algorithm
*   The logic and state transitions are identical to the previous 3D DP approach.
*   Instead of a `dp[n+1][...][...]` table, we use two tables, `dp[6][16]` and `prev_dp[6][16]`.
*   Initialize `prev_dp` for the base case `i=1`.
*   In each iteration `i` from 2 to `n`, we calculate the `dp` table (for state `i`) using the values from the `prev_dp` table (for state `i-1`).
*   After computing the values for the current iteration, we copy the `dp` table to `prev_dp` to prepare for the next iteration.
*   This reduces the space from being proportional to `n` to being constant (with respect to `n`).

## 2D Dynamic Programming with Subtraction
This is a more efficient approach that redefines the DP state to reduce the dimensions of the table and improve the time complexity. Instead of tracking the consecutive count explicitly in the state, we calculate the number of valid sequences by taking the total possible sequences and subtracting the invalid ones. This 'subtraction' principle leads to a faster solution.
**Time:** O(n * faces). This is a significant improvement as we removed the dependency on `max_rollMax` from the loops. · **Space:** O(n * faces). We use a 2D DP table of size `(n+1) x 6` and a sum array of size `n+1`.
**Pros:** Much faster time complexity than the 3D DP approaches.; The DP state is simpler (2D vs 3D).
**Cons:** Still uses linear space with respect to `n`.; The recurrence relation is slightly more complex to derive.
### Explanation
Let `dp[i][j]` be the number of valid sequences of length `i` ending with face `j`. Let `S[i]` be the total number of valid sequences of length `i`.

To calculate `dp[i][j]`, we can start with the total number of ways to form a sequence of length `i-1` (`S[i-1]`) and append `j`. This gives us `S[i-1]` potential sequences.

However, this includes invalid sequences where `j` is rolled more than `rollMax[j]` consecutive times. We must subtract these. An invalid sequence of length `i` ending with `rollMax[j] + 1` consecutive `j`'s must have the form `... p j j ... j`, where `p != j`. The prefix `... p` has length `i - (rollMax[j] + 1)`. The number of such prefixes is the number of valid sequences of that length that do not end in `j`, which is `S[i - rollMax[j] - 1] - dp[i - rollMax[j] - 1][j]`. This gives us our recurrence.

```java
class Solution {
    public int dieSimulator(int n, int[] rollMax) {
        long MOD = 1_000_000_007;
        long[][] dp = new long[n + 1][6];
        long[] sum = new long[n + 1];
        sum[0] = 1;

        for (int i = 1; i <= n; i++) {
            long currentSum = 0;
            for (int j = 0; j < 6; j++) {
                // Initially, assume we can append j to any valid sequence of length i-1
                dp[i][j] = sum[i - 1];
                
                int k = rollMax[j];
                if (i > k) {
                    // Subtract sequences of length i-k-1 not ending with j
                    long toSubtract = (sum[i - k - 1] - dp[i - k - 1][j] + MOD) % MOD;
                    dp[i][j] = (dp[i][j] - toSubtract + MOD) % MOD;
                } else if (i == k) {
                    // Subtract the sequence of all j's
                    dp[i][j] = (dp[i][j] - 1 + MOD) % MOD;
                }
                currentSum = (currentSum + dp[i][j]) % MOD;
            }
            sum[i] = currentSum;
        }

        return (int) sum[n];
    }
}
```
### Algorithm
*   Define `dp[i][j]` as the number of valid sequences of length `i` ending with face `j`.
*   Define `S[i]` as the total number of valid sequences of length `i`, which is `sum(dp[i][p])` over all faces `p`.
*   Base case: `S[0] = 1` (for the empty sequence).
*   Iterate `i` from 1 to `n`:
    *   For each face `j` from 0 to 5:
        *   Start with `dp[i][j] = S[i-1]`, which is the count if there were no constraints.
        *   Let `k = rollMax[j]`. We must subtract the invalid sequences that end with more than `k` consecutive `j`'s.
        *   If `i > k`, the number of invalid sequences is the number of valid sequences of length `i-k-1` that did not end in `j`. This is `S[i-k-1] - dp[i-k-1][j]`. Subtract this from `dp[i][j]`.
        *   If `i == k`, there is exactly one invalid sequence (all `j`'s). Subtract 1.
    *   Calculate `S[i]` by summing `dp[i][j]` over all `j`.
*   Return `S[n]`.

## Space-Optimized 2D DP with Subtraction
This is the most efficient approach, building upon the 2D DP with subtraction method. It optimizes the space complexity to be constant by noticing that we only need to remember a fixed number of previous states to calculate the current state. By using circular arrays, we can discard old, unnecessary information and keep the memory footprint small and constant, regardless of `n`.
**Time:** O(n * faces). The time complexity is the same as the previous approach and is optimal. · **Space:** O(max_rollMax * faces). This is constant space as it does not depend on `n`.
**Pros:** Optimal time complexity.; Optimal constant space complexity.
**Cons:** The logic with circular arrays and modulo arithmetic can be slightly more complex to implement correctly.
### Explanation
This approach refines the 2D DP with Subtraction method by optimizing its space usage. The recurrence relation `dp[i][j]` depends on values from `dp[i-1]` and `dp[i - rollMax[j] - 1]`. The maximum look-back required is determined by the largest value in `rollMax`, which is at most 15. This means we only need to store the results for the last 16 or so steps.

We can implement this using circular arrays for our `dp` and `sum` tables. A circular array of a fixed size (e.g., 17, which is `max(rollMax) + 2`) is sufficient. We use the modulo operator on the current roll index `i` to map it to an index in our small arrays. For example, the state for roll `i` is stored at index `i % 17`. This clever trick reduces the space complexity from `O(n * faces)` to `O(max_rollMax * faces)`, which is constant.

```java
class Solution {
    public int dieSimulator(int n, int[] rollMax) {
        long MOD = 1_000_000_007;
        // We only need to store the last 16 states (max(rollMax) + 1)
        // Use a buffer of size 17 for safety with modulo arithmetic
        int bufferSize = 17; 
        long[][] dp = new long[bufferSize][6];
        long[] sum = new long[bufferSize];
        sum[0] = 1;

        for (int i = 1; i <= n; i++) {
            int i_mod = i % bufferSize;
            int i_minus_1_mod = (i - 1 + bufferSize) % bufferSize;
            long currentSum = 0;

            for (int j = 0; j < 6; j++) {
                dp[i_mod][j] = sum[i_minus_1_mod];
                
                int k = rollMax[j];
                if (i > k) {
                    int i_minus_k_minus_1_mod = (i - k - 1 + bufferSize) % bufferSize;
                    long toSubtract = (sum[i_minus_k_minus_1_mod] - dp[i_minus_k_minus_1_mod][j] + MOD) % MOD;
                    dp[i_mod][j] = (dp[i_mod][j] - toSubtract + MOD) % MOD;
                } else if (i == k) {
                    dp[i_mod][j] = (dp[i_mod][j] - 1 + MOD) % MOD;
                }
                currentSum = (currentSum + dp[i_mod][j]) % MOD;
            }
            sum[i_mod] = currentSum;
        }

        return (int) sum[n % bufferSize];
    }
}
```
### Algorithm
*   The logic is identical to the 2D DP with Subtraction approach.
*   Observe that `dp[i]` depends on `dp[i-1]` and `dp[i - k - 1]`, where `k` is `rollMax[j]`.
*   The maximum look-back required is `max(rollMax) + 1`. Since `max(rollMax)` is at most 15, we only need to store the last ~16 states.
*   We use circular arrays for `dp` and `sum` tables to store only this recent history. The size of these circular arrays would be `max(rollMax) + 2`.
*   We use the modulo operator on the current roll index `i` to map it to an index in our small circular arrays (e.g., `dp[i % buffer_size][j]`).
*   This reduces the space complexity from `O(n * faces)` to `O(max_rollMax * faces)`, which is constant.

# Solutions
### Java

```java
class Solution {
private
  Integer[][][] f;
private
  int[] rollMax;
public
  int dieSimulator(int n, int[] rollMax) {
    f = new Integer[n][7][16];
    this.rollMax = rollMax;
    return dfs(0, 0, 0);
  }
private
  int dfs(int i, int j, int x) {
    if (i >= f.length) {
      return 1;
    }
    if (f[i][j][x] != null) {
      return f[i][j][x];
    }
    long ans = 0;
    for (int k = 1; k <= 6; ++k) {
      if (k != j) {
        ans += dfs(i + 1, k, 1);
      } else if (x < rollMax[j - 1]) {
        ans += dfs(i + 1, j, x + 1);
      }
    }
    ans %= 1000000007;
    return f[i][j][x] = (int)ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int dieSimulator(int n, vector<int> &rollMax) {
    int f[n][7][16];
    memset(f, 0, sizeof f);
    const int mod = 1e9 + 7;
    function<int(int, int, int)> dfs = [&](int i, int j, int x) -> int {
      if (i >= n) {
        return 1;
      }
      if (f[i][j][x]) {
        return f[i][j][x];
      }
      long ans = 0;
      for (int k = 1; k <= 6; ++k) {
        if (k != j) {
          ans += dfs(i + 1, k, 1);
        } else if (x < rollMax[j - 1]) {
          ans += dfs(i + 1, j, x + 1);
        }
      }
      ans %= mod;
      return f[i][j][x] = ans;
    };
    return dfs(0, 0, 0);
  }
};

```

### Python

```python
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int: @ cache def dfs(i, j, x): if i >= n: return 1 ans = 0 for k in range(1, 7): if k != j: ans += dfs(i + 1, k, 1) elif x < rollMax[j - 1]: ans += dfs(i + 1, j, x + 1) return ans % (10 ** 9 + 7) return dfs(0, 0, 0)

```