Dice Roll Simulation: Constrained DP

You have a die with 6 faces numbered 1 through 6. You are given n (the number of rolls) and an array rollMax of length 6 where rollMax[i] is the maximum number of consecutive times face i + 1 can appear. Return the number of distinct sequences you can roll, modulo 10^9 + 7.

This is LeetCode 1223: Dice Roll Simulation. For example, with n = 2 and rollMax = [1,1,2,2,2,3], face 1 cannot appear twice in a row, but face 3 can appear up to twice consecutively. The answer is 34.

Why this problem matters

Most DP problems have a simple state: the current index, the remaining capacity, or the last element. Dice Roll Simulation forces you to track an extra dimension, the consecutive count. This "constrained state" pattern appears in many harder DP problems. Once you learn to add a third dimension for tracking how many times in a row something has happened, you unlock a whole family of problems that would otherwise feel impossible to model.

The constraint here is not about what you can pick. You can always pick any face. The constraint is about how many times in a row you can pick the same face. That subtle distinction means the DP state needs to encode not just what happened last, but how long the current streak has been going.

The key insight

A naive 2D DP where dp[i][j] counts sequences of length i ending with face j is not enough. Consider face 3 with rollMax = 2. If the last two rolls were both 3, you cannot roll 3 again. But if only the last roll was 3, you can. The 2D table cannot distinguish these cases.

The fix is to add a third dimension. Define dp[i][j][k] as the number of valid sequences of length i that end with face j having been rolled k consecutive times. Now the state carries exactly the information you need to decide whether rolling face j again is legal.

The transitions are:

• Switch face: if the new face j differs from the previous face, consecutive count resets to 1. dp[i][j][1] += dp[i-1][f][k] for all f != j and all valid k.
• Extend streak: if you roll the same face j again and k + 1 is within rollMax[j-1], the count increments. dp[i][j][k+1] += dp[i-1][j][k].

The solution

def dieSimulator(n, rollMax):
    MOD = 10**9 + 7
    max_consec = max(rollMax)
    dp = [[[0] * (max_consec + 1) for _ in range(6)] for _ in range(n + 1)]

    for j in range(6):
        dp[1][j][1] = 1

    for i in range(2, n + 1):
        for j in range(6):
            for f in range(6):
                if f != j:
                    for k in range(1, rollMax[f] + 1):
                        dp[i][j][1] = (dp[i][j][1] + dp[i - 1][f][k]) % MOD
            for k in range(2, rollMax[j] + 1):
                dp[i][j][k] = dp[i - 1][j][k - 1]

    result = 0
    for j in range(6):
        for k in range(1, rollMax[j] + 1):
            result = (result + dp[n][j][k]) % MOD
    return result

The outer loop iterates over sequence lengths from 2 to n. For each position, you fill every (face, consecutive count) pair. The "switch" transition sums over all other faces and their valid consecutive counts. The "extend" transition simply copies from the previous consecutive count.

Visual walkthrough

Let's trace through n = 2 and rollMax = [1,1,2,2,2,3] step by step. The key question at each roll is: which (face, consecutive count) pairs are valid, and how do they combine?

Notice how faces 1 and 2 contribute fewer sequences because their rollMax is 1. They can never extend a streak, so the only way to end on face 1 or 2 after two rolls is to switch from something else. Faces 3 through 6 get an extra sequence each from the extend transition.

Complexity analysis

The time complexity has three nested factors: n rolls, 6 faces, and up to max(rollMax) consecutive counts. The switch transition adds another factor of 6 in the worst case, but the optimized version (precomputing totals) brings it back down. For the space, you only need two layers of the DP table (current roll and previous roll), giving O(6 * max(rollMax)). Since rollMax[i] is at most 15 per the constraints, the table fits comfortably in memory.

The building blocks

1. State definition with consecutive count

dp = [[[0] * (max_consec + 1) for _ in range(6)] for _ in range(n + 1)]

for j in range(6):
    dp[1][j][1] = 1

The third dimension k tracks how deep you are into a streak. Base case: after one roll, every face has been rolled exactly once consecutively. This pattern of adding a dimension to encode "how many times in a row" is the core of constrained state DP. You will see the same idea in problems like Count Vowels Permutation, where the constraint is about which transitions are allowed based on the current state.

2. Transition with constraint checking

for j in range(6):
    for f in range(6):
        if f != j:
            for k in range(1, rollMax[f] + 1):
                dp[i][j][1] = (dp[i][j][1] + dp[i - 1][f][k]) % MOD
    for k in range(2, rollMax[j] + 1):
        dp[i][j][k] = dp[i - 1][j][k - 1]

Two cases, cleanly separated. Switching face resets consecutive count to 1 and draws from every valid state of every other face. Extending a streak increments the count by 1 and only applies when the new count is still within the limit. The constraint check is implicit in the loop bound: k only goes up to rollMax[j], so you never create an invalid state.

Edge cases

• All rollMax values are 1: no face can repeat consecutively. The problem reduces to counting permutations where no two adjacent elements are the same. For n = 1 the answer is 6. For n = 2 the answer is 30 (6 choices for first, 5 for second).
• n = 1: the answer is always 6, regardless of rollMax, since a single roll cannot violate any consecutive constraint.
• One rollMax is very large: if rollMax[0] = 15 (the max allowed), face 1 can appear up to 15 times in a row. The DP table grows in the k dimension but the logic stays the same.
• All rollMax values equal n: no constraint is ever binding. Every sequence of length n is valid, giving 6^n mod (10^9 + 7).
• Modular arithmetic: the counts grow fast. Always take mod at every addition to avoid overflow in languages with fixed-size integers.

From understanding to recall

You now understand why a third DP dimension is necessary, how the switch and extend transitions work, and how the rollMax constraint gets enforced through loop bounds. But understanding the logic once is not the same as reproducing it under pressure. In an interview, you need to remember that the state is (roll, face, consecutive), that switching resets k to 1, and that extending increments k by 1.

The constrained state DP pattern shows up in many problems beyond dice. Count Vowels Permutation constrains which letters can follow which. Student Attendance Record II constrains how many consecutive absences are allowed. Every time you see "at most X in a row," you should think of adding a consecutive-count dimension. Drilling this pattern with spaced repetition until the state definition and transitions are automatic is the fastest way to own this category of problems.

Related posts

• Count Vowels Permutation - State machine DP with transition rules
• Decode Ways - Counting sequences with constraints
• Coin Change - DP with multiple choices at each step

The constrained state DP pattern is one of roughly 60 reusable building blocks in the CodeBricks system. You practice it with spaced repetition until the three-dimensional state definition and the switch/extend transitions are second nature. That kind of fluency is what separates "I can solve it if I think hard enough" from "I see the pattern instantly."