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.

Examples

Example 1

1
2
3

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

1
2

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

Example 3

1
2

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

Solution

Method 1 – Dynamic Programming (Top-Down with Memoization)

Intuition

We use dynamic programming to count the number of valid sequences. The key is to track, for each roll, which number was last rolled and how many times it has appeared consecutively. By memoizing the state (rolls_left, last_num, last_count), we avoid redundant calculations.

Approach

  1. Define a recursive function dp(rolls_left, last_num, last_count):
  • rolls_left: Number of rolls remaining.
  • last_num: The last number rolled (0 to 5 for dice faces).
  • last_count: How many times last_num has appeared consecutively.
  1. Base case: If rolls_left == 0, return 1 (valid sequence).
  2. For each possible next number (0 to 5):
  • If next_num == last_num and last_count < rollMax[next_num], continue the streak.
  • If next_num != last_num, start a new streak.
  • Skip if the streak would exceed rollMax.
  1. Memoize results for each state to avoid recomputation.
  2. Sum all valid ways for all possible starting numbers.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
   int dieSimulator(int n, vector<int>& rollMax) {
      const int MOD = 1e9 + 7;
      int dp[501][6][16] = {};
      memset(dp, -1, sizeof(dp));
      function<int(int, int, int)> dfs = [&](int left, int last, int cnt) -> int {
        if (left == 0) return 1;
        if (last != -1 && dp[left][last][cnt] != -1) return dp[left][last][cnt];
        int ans = 0;
        for (int i = 0; i < 6; ++i) {
           if (i == last) {
              if (cnt < rollMax[i])
                ans = (ans + dfs(left - 1, i, cnt + 1)) % MOD;
           } else {
              ans = (ans + dfs(left - 1, i, 1)) % MOD;
           }
        }
        if (last != -1) dp[left][last][cnt] = ans;
        return ans;
      };
      return dfs(n, -1, 0);
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

func dieSimulator(n int, rollMax []int) int {
   mod := int(1e9 + 7)
   dp := make([][][]int, n+1)
   for i := range dp {
      dp[i] = make([][]int, 7)
      for j := range dp[i] {
        dp[i][j] = make([]int, 16)
        for k := range dp[i][j] {
           dp[i][j][k] = -1
        }
      }
   }
   var dfs func(left, last, cnt int) int
   dfs = func(left, last, cnt int) int {
      if left == 0 {
        return 1
      }
      if last != -1 && dp[left][last][cnt] != -1 {
        return dp[left][last][cnt]
      }
      ans := 0
      for i := 0; i < 6; i++ {
        if i == last {
           if cnt < rollMax[i] {
              ans = (ans + dfs(left-1, i, cnt+1)) % mod
           }
        } else {
           ans = (ans + dfs(left-1, i, 1)) % mod
        }
      }
      if last != -1 {
        dp[left][last][cnt] = ans
      }
      return ans
   }
   return dfs(n, -1, 0)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
   public int dieSimulator(int n, int[] rollMax) {
      int MOD = 1000000007;
      Integer[][][] dp = new Integer[n+1][7][16];
      return dfs(n, -1, 0, rollMax, dp, MOD);
   }
   private int dfs(int left, int last, int cnt, int[] rollMax, Integer[][][] dp, int MOD) {
      if (left == 0) return 1;
      if (last != -1 && dp[left][last][cnt] != null) return dp[left][last][cnt];
      int ans = 0;
      for (int i = 0; i < 6; i++) {
        if (i == last) {
           if (cnt < rollMax[i])
              ans = (ans + dfs(left-1, i, cnt+1, rollMax, dp, MOD)) % MOD;
        } else {
           ans = (ans + dfs(left-1, i, 1, rollMax, dp, MOD)) % MOD;
        }
      }
      if (last != -1) dp[left][last][cnt] = ans;
      return ans;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
   fun dieSimulator(n: Int, rollMax: IntArray): Int {
      val MOD = 1_000_000_007
      val dp = Array(n+1) { Array(7) { IntArray(16) { -1 } } }
      fun dfs(left: Int, last: Int, cnt: Int): Int {
        if (left == 0) return 1
        if (last != -1 && dp[left][last][cnt] != -1) return dp[left][last][cnt]
        var ans = 0
        for (i in 0..5) {
           if (i == last) {
              if (cnt < rollMax[i])
                ans = (ans + dfs(left-1, i, cnt+1)) % MOD
           } else {
              ans = (ans + dfs(left-1, i, 1)) % MOD
           }
        }
        if (last != -1) dp[left][last][cnt] = ans
        return ans
      }
      return dfs(n, -1, 0)
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
   def dieSimulator(self, n: int, rollMax: list[int]) -> int:
      MOD = 10**9 + 7
      from functools import lru_cache

      @lru_cache(maxsize=None)
      def dp(left: int, last: int, cnt: int) -> int:
        if left == 0:
           return 1
        ans = 0
        for i in range(6):
           if i == last:
              if cnt < rollMax[i]:
                ans = (ans + dp(left-1, i, cnt+1)) % MOD
           else:
              ans = (ans + dp(left-1, i, 1)) % MOD
        return ans

      return dp(n, -1, 0)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

impl Solution {
   pub fn die_simulator(n: i32, roll_max: Vec<i32>) -> i32 {
      const MOD: i32 = 1_000_000_007;
      let n = n as usize;
      let mut dp = vec![vec![vec![-1; 16]; 7]; n+1];
      fn dfs(left: usize, last: i32, cnt: usize, roll_max: &Vec<i32>, dp: &mut Vec<Vec<Vec<i32>>>) -> i32 {
        if left == 0 { return 1; }
        if last != -1 && dp[left][last as usize][cnt] != -1 {
           return dp[left][last as usize][cnt];
        }
        let mut ans = 0;
        for i in 0..6 {
           if i as i32 == last {
              if cnt < roll_max[i] as usize {
                ans = (ans + dfs(left-1, i as i32, cnt+1, roll_max, dp)) % MOD;
              }
           } else {
              ans = (ans + dfs(left-1, i as i32, 1, roll_max, dp)) % MOD;
           }
        }
        if last != -1 {
           dp[left][last as usize][cnt] = ans;
        }
        ans
      }
      dfs(n, -1, 0, &roll_max, &mut dp)
   }
}

Complexity

  • ⏰ Time complexity: O(n * 6 * maxRoll) where maxRoll is the maximum value in rollMax.
  • 🧺 Space complexity: O(n * 6 * maxRoll) due to memoization.

Method 2 – Dynamic Programming (Bottom-Up Tabulation)

Intuition

We use bottom-up dynamic programming to build the solution iteratively. Instead of recursion, we fill a DP table where each entry represents the number of ways to reach a certain state (rolls left, last number, consecutive count). This avoids stack overhead and is often more efficient.

Approach

  1. Define a 3D DP array dp[roll][face][count]:
  • roll: Number of rolls completed (from 1 to n).
  • face: The current face (0 to 5).
  • count: How many times face has appeared consecutively (from 1 to rollMax[face]).
  1. Initialize dp[1][face][1] = 1 for all faces (first roll can be any face, count is 1).
  2. For each roll from 2 to n:
  • For each face:
    • For each possible consecutive count:
    • If continuing the same face, increment count (if allowed by rollMax).
    • If switching to a new face, reset count to 1.
  1. Sum all valid ways for the last roll across all faces and counts.
  2. Return the result modulo 1e9+7.
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
   int dieSimulator(int n, vector<int>& rollMax) {
      const int MOD = 1e9 + 7;
      int dp[501][6][16] = {};
      for (int f = 0; f < 6; ++f)
        dp[1][f][1] = 1;
      for (int r = 2; r <= n; ++r) {
        for (int f = 0; f < 6; ++f) {
           for (int pf = 0; pf < 6; ++pf) {
              if (pf == f) continue;
              for (int cnt = 1; cnt <= rollMax[pf]; ++cnt) {
                dp[r][f][1] = (dp[r][f][1] + dp[r-1][pf][cnt]) % MOD;
              }
           }
           for (int cnt = 2; cnt <= rollMax[f]; ++cnt) {
              dp[r][f][cnt] = (dp[r][f][cnt] + dp[r-1][f][cnt-1]) % MOD;
           }
        }
      }
      int ans = 0;
      for (int f = 0; f < 6; ++f)
        for (int cnt = 1; cnt <= rollMax[f]; ++cnt)
           ans = (ans + dp[n][f][cnt]) % MOD;
      return ans;
   }
};
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

func dieSimulator(n int, rollMax []int) int {
   mod := int(1e9 + 7)
   dp := make([][][]int, n+1)
   for i := range dp {
      dp[i] = make([][]int, 6)
      for j := range dp[i] {
        dp[i][j] = make([]int, 16)
      }
   }
   for f := 0; f < 6; f++ {
      dp[1][f][1] = 1
   }
   for r := 2; r <= n; r++ {
      for f := 0; f < 6; f++ {
        for pf := 0; pf < 6; pf++ {
           if pf == f {
              continue
           }
           for cnt := 1; cnt <= rollMax[pf]; cnt++ {
              dp[r][f][1] = (dp[r][f][1] + dp[r-1][pf][cnt]) % mod
           }
        }
        for cnt := 2; cnt <= rollMax[f]; cnt++ {
           dp[r][f][cnt] = (dp[r][f][cnt] + dp[r-1][f][cnt-1]) % mod
        }
      }
   }
   ans := 0
   for f := 0; f < 6; f++ {
      for cnt := 1; cnt <= rollMax[f]; cnt++ {
        ans = (ans + dp[n][f][cnt]) % mod
      }
   }
   return ans
}
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
   public int dieSimulator(int n, int[] rollMax) {
      int MOD = 1_000_000_007;
      int[][][] dp = new int[n+1][6][16];
      for (int f = 0; f < 6; f++)
        dp[1][f][1] = 1;
      for (int r = 2; r <= n; r++) {
        for (int f = 0; f < 6; f++) {
           for (int pf = 0; pf < 6; pf++) {
              if (pf == f) continue;
              for (int cnt = 1; cnt <= rollMax[pf]; cnt++) {
                dp[r][f][1] = (dp[r][f][1] + dp[r-1][pf][cnt]) % MOD;
              }
           }
           for (int cnt = 2; cnt <= rollMax[f]; cnt++) {
              dp[r][f][cnt] = (dp[r][f][cnt] + dp[r-1][f][cnt-1]) % MOD;
           }
        }
      }
      int ans = 0;
      for (int f = 0; f < 6; f++)
        for (int cnt = 1; cnt <= rollMax[f]; cnt++)
           ans = (ans + dp[n][f][cnt]) % MOD;
      return ans;
   }
}
Kotlin
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
   fun dieSimulator(n: Int, rollMax: IntArray): Int {
      val MOD = 1_000_000_007
      val dp = Array(n+1) { Array(6) { IntArray(16) } }
      for (f in 0..5) dp[1][f][1] = 1
      for (r in 2..n) {
        for (f in 0..5) {
           for (pf in 0..5) {
              if (pf == f) continue
              for (cnt in 1..rollMax[pf]) {
                dp[r][f][1] = (dp[r][f][1] + dp[r-1][pf][cnt]) % MOD
              }
           }
           for (cnt in 2..rollMax[f]) {
              dp[r][f][cnt] = (dp[r][f][cnt] + dp[r-1][f][cnt-1]) % MOD
           }
        }
      }
      var ans = 0
      for (f in 0..5)
        for (cnt in 1..rollMax[f])
           ans = (ans + dp[n][f][cnt]) % MOD
      return ans
   }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
   def dieSimulator(self, n: int, rollMax: list[int]) -> int:
      MOD = 10**9 + 7
      dp: list[list[list[int]]] = [[[0]*16 for _ in range(6)] for _ in range(n+1)]
      for f in range(6):
        dp[1][f][1] = 1
      for r in range(2, n+1):
        for f in range(6):
           for pf in range(6):
              if pf == f:
                continue
              for cnt in range(1, rollMax[pf]+1):
                dp[r][f][1] = (dp[r][f][1] + dp[r-1][pf][cnt]) % MOD
           for cnt in range(2, rollMax[f]+1):
              dp[r][f][cnt] = (dp[r][f][cnt] + dp[r-1][f][cnt-1]) % MOD
      ans = 0
      for f in range(6):
        for cnt in range(1, rollMax[f]+1):
           ans = (ans + dp[n][f][cnt]) % MOD
      return ans
Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

impl Solution {
   pub fn die_simulator(n: i32, roll_max: Vec<i32>) -> i32 {
      const MOD: i32 = 1_000_000_007;
      let n = n as usize;
      let mut dp = vec![vec![vec![0; 16]; 6]; n+1];
      for f in 0..6 {
        dp[1][f][1] = 1;
      }
      for r in 2..=n {
        for f in 0..6 {
           for pf in 0..6 {
              if pf == f { continue; }
              for cnt in 1..=roll_max[pf] as usize {
                dp[r][f][1] = (dp[r][f][1] + dp[r-1][pf][cnt]) % MOD;
              }
           }
           for cnt in 2..=roll_max[f] as usize {
              dp[r][f][cnt] = (dp[r][f][cnt] + dp[r-1][f][cnt-1]) % MOD;
           }
        }
      }
      let mut ans = 0;
      for f in 0..6 {
        for cnt in 1..=roll_max[f] as usize {
           ans = (ans + dp[n][f][cnt]) % MOD;
        }
      }
      ans
   }
}

Complexity

  • ⏰ Time complexity: O(n * 6 * maxRoll * 6), where maxRoll is the maximum in rollMax.
  • 🧺 Space complexity: O(n * 6 * maxRoll)