Dice Roll Simulation

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

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