#1223

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Dice Roll Simulation

Calculate all valid sequences of n dice rolls with consecutive roll constraints using state transition dynamic programming efficiently.

array dynamic programming

Problem Statement

You are given an integer n representing the total number of dice rolls and an array rollMax of length 6, where rollMax[i] indicates the maximum times the number i+1 can appear consecutively. The task is to count all distinct sequences of exactly n rolls that obey these constraints. Each sequence must differ by at least one roll from any other sequence to be considered unique.

Implement a function that returns the total number of valid sequences modulo 10^9 + 7. Consider that sequences like [1,1] may be invalid if rollMax restricts consecutive repetitions, while sequences like [1,2] or [2,1] remain valid. Your solution should account for all n-length sequences respecting the rollMax limits efficiently using dynamic programming.

Examples

Example 1

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

Output: 34

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 details omitted.

Example 3

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

Output: 181

Example details omitted.

Constraints

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

Solution Approach

Define DP State

Use a three-dimensional DP array dp[pos][last][count] where pos is the current roll index, last is the last number rolled, and count is the consecutive occurrences of last. Initialize dp[0][i][1] = 1 for all valid i to represent sequences starting with each number.

State Transitions

For each roll position, iterate through all numbers 1-6. If the next number equals last, increment count only if it does not exceed rollMax[last]. If the next number differs, reset count to 1. Accumulate counts from previous states to build dp[pos][next][new_count].

Compute Result

Sum all dp[n][last][count] values for all last in 1-6 and count within rollMax[last]. Apply modulo 10^9 + 7 at every accumulation step to avoid integer overflow. This yields the total number of valid sequences respecting all rollMax constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on n, the number of dice rolls, and the maximum rollMax values because the DP array tracks positions, last numbers, and consecutive counts. Space complexity also scales with n * 6 * max(rollMax) for storing intermediate DP states.

What Interviewers Usually Probe

Check if you are tracking consecutive rolls correctly and respecting rollMax limits.
Consider how to reduce unnecessary iterations by limiting counts according to rollMax.
Think about modular arithmetic to prevent integer overflow for large n.

Common Pitfalls or Variants

Common pitfalls

Not resetting consecutive count when the next roll differs from the last number.
Exceeding rollMax for a number by miscounting consecutive occurrences.
Forgetting to apply modulo 10^9 + 7 after each DP accumulation step.

Follow-up variants

Dice sequences with varying die faces, not fixed at 6, with per-face rollMax constraints.
Count sequences where only specific numbers have consecutive roll limits, while others are unrestricted.
Compute sequences where the order matters, but consecutive repetitions are allowed up to different rollMax thresholds for subsets of numbers.

FAQ

What is the main pattern to solve Dice Roll Simulation?

The main pattern is state transition dynamic programming, where each DP state tracks the last number rolled and its consecutive count.

How do I handle large n in Dice Roll Simulation?

Use modulo 10^9 + 7 at each DP accumulation to manage large numbers and prevent integer overflow efficiently.

Can sequences with different consecutive numbers be merged in DP?

No, each sequence state must track the last number and its consecutive count separately to respect rollMax constraints.

Is it necessary to initialize DP for all numbers at position 0?

Yes, each number can start a valid sequence, so initialize dp[0][i][1] = 1 for all numbers 1 through 6.

How does GhostInterview avoid common pitfalls in this problem?

It helps by highlighting invalid consecutive counts, enforcing rollMax limits, and checking modular arithmetic throughout the DP table.

terminal

Solution

Solution 1: Memoization Search

We can design a function $dfs(i, j, x)$ to represent the number of schemes starting from the $i$-th dice roll, with the current dice roll being $j$, and the number of consecutive times $j$ is rolled being $x$. The range of $j$ is $[1, 6]$, and the range of $x$ is $[1, rollMax[j - 1]]$. The answer is $dfs(0, 0, 0)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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)

Solution 2: Dynamic Programming

We can change the memoization search in Solution 1 to dynamic programming.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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)

Continue Practicing

#1218 longest arithmetic subsequence of given difference #1235 maximum profit in job scheduling #1191 k concatenation maximum sum