HardArrayDynamic Programming

Dice Roll Simulation

1 approach, code in every language

A six-sided die shows faces 1 through 6. You are given an integer n and an array rollMax of length 6, where rollMax[i] is the maximum number of times the face (i + 1) is allowed to appear consecutively.

You roll the die exactly n times, producing a sequence of faces. A sequence is valid only if no face ever appears more than its allowed number of consecutive repetitions. Count the number of distinct valid sequences of length n. Because the count can be very large, return it modulo 10^9 + 7.

Example 1

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

Output: 34

There are 36 sequences of length two. Face 1 and face 2 may each appear at most once in a row, so the pairs (1,1) and (2,2) are forbidden. Removing those two invalid sequences leaves 34.

Example 2

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

Output: 30

No face may repeat consecutively, so all six doubles are forbidden. That leaves 36 - 6 = 30 valid sequences.

Constraints

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

Dynamic Programming over Face and Run Length

Track how many valid sequences end with a given face repeated a given number of consecutive times, then extend one roll at a time.

Loading animation…

Intuition

A sequence stays valid based only on which face it ends with and how many times that face has repeated so far, so those two pieces of information form the state. Let dp[face][count] be the number of valid sequences of the current length that end with face repeated count times consecutively. To add another roll we either repeat the same face, which pushes count up by one but is only allowed while count stays within rollMax[face], or we switch to any other face, which starts a fresh run of length one. Switching from a state to a different face contributes that state's whole count to the new face's run-length-one bucket. Summing every reachable state after n rolls gives the total number of valid sequences, and we reduce modulo 10^9 + 7 at each addition to keep numbers bounded.

Algorithm walkthrough

1Initialize length-one sequences: for every face f, dp[f][1] = 1, since a single roll is a valid run of length one.
2Repeat the extension step n - 1 times to grow the sequences from length one up to length n.
3For each state (f, c) with a positive count, rolling f again moves to (f, c + 1) but only when c + 1 <= rollMax[f].
4For each state (f, c), rolling any different face g adds the state's count into (g, 1), starting a new run.
5Accumulate all transitions into a fresh table, taking every addition modulo 10^9 + 7.
6After all extensions, sum every dp[f][c] to obtain the count of valid length-n sequences.

Implementation

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10**9 + 7
        dp = [[0] * (rollMax[f] + 1) for f in range(6)]
        for f in range(6):
            dp[f][1] = 1
        for _ in range(n - 1):
            ndp = [[0] * (rollMax[f] + 1) for f in range(6)]
            for f in range(6):
                for c in range(1, rollMax[f] + 1):
                    ways = dp[f][c]
                    if ways == 0:
                        continue
                    if c + 1 <= rollMax[f]:
                        ndp[f][c + 1] = (ndp[f][c + 1] + ways) % MOD
                    for g in range(6):
                        if g != f:
                            ndp[g][1] = (ndp[g][1] + ways) % MOD
            dp = ndp
        return sum(sum(row) for row in dp) % MOD

Time

O(n * 36 * maxRoll)

Space

O(6 * maxRoll)

For each of the n rolls we iterate over 6 faces and up to rollMax run lengths, and each state fans out to the 6 faces. With maxRoll <= 15 this is effectively linear in n.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free