Dice Roll Simulation

hard dynamic programming counting

Problem

A die is rolled n times. The array rollMax has length 6, where rollMax[k] is the maximum number of times the face value (k + 1) may appear consecutively. Return the number of distinct sequences of length n that obey every consecutive limit, modulo 10⁹ + 7.

Inputn = 2, rollMax = [1, 1, 2, 2, 2, 3]

Output34

There are 6 × 6 = 36 sequences of length 2; the pairs (1,1) and (2,2) are forbidden because faces 1 and 2 may repeat at most once, leaving 34.

n (rolls)

rollMax (6 comma-separated limits)

def dieSimulator(n, rollMax):
    MOD = 10**9 + 7
    # dp[f][c] = sequences ending in face f with c consecutive f's
    dp = [[0] * (rollMax[f] + 1) for f in range(6)]
    for f in range(6):
        dp[f][1] = 1
    for _ in range(n - 1):
        nxt = [[0] * (rollMax[f] + 1) for f in range(6)]
        for f in range(6):
            total = sum(dp[g][c] for g in range(6) for c in range(1, rollMax[g] + 1))
            same = sum(dp[f][c] for c in range(1, rollMax[f] + 1))
            for c in range(1, rollMax[f] + 1):
                if c == 1:
                    nxt[f][1] = (total - same) % MOD
                else:
                    nxt[f][c] = dp[f][c - 1]
        dp = nxt
    return sum(dp[f][c] for f in range(6) for c in range(1, rollMax[f] + 1)) % MOD

function dieSimulator(n, rollMax) {
  const MOD = 1000000007n;
  let dp = rollMax.map(m => new Array(m + 1).fill(0n));
  for (let f = 0; f < 6; f++) dp[f][1] = 1n;
  for (let r = 1; r < n; r++) {
    const nxt = rollMax.map(m => new Array(m + 1).fill(0n));
    let total = 0n;
    for (let g = 0; g < 6; g++)
      for (let c = 1; c <= rollMax[g]; c++) total += dp[g][c];
    for (let f = 0; f < 6; f++) {
      let same = 0n;
      for (let c = 1; c <= rollMax[f]; c++) same += dp[f][c];
      for (let c = 1; c <= rollMax[f]; c++)
        nxt[f][c] = c === 1 ? ((total - same) % MOD + MOD) % MOD : dp[f][c - 1];
    }
    dp = nxt;
  }
  let ans = 0n;
  for (let f = 0; f < 6; f++)
    for (let c = 1; c <= rollMax[f]; c++) ans = (ans + dp[f][c]) % MOD;
  return Number(ans);
}

class Solution {
    public int dieSimulator(int n, int[] rollMax) {
        final long MOD = 1_000_000_007L;
        long[][] dp = new long[6][];
        for (int f = 0; f < 6; f++) { dp[f] = new long[rollMax[f] + 1]; dp[f][1] = 1; }
        for (int r = 1; r < n; r++) {
            long[][] nxt = new long[6][];
            long total = 0;
            for (int g = 0; g < 6; g++)
                for (int c = 1; c <= rollMax[g]; c++) total += dp[g][c];
            total %= MOD;
            for (int f = 0; f < 6; f++) {
                nxt[f] = new long[rollMax[f] + 1];
                long same = 0;
                for (int c = 1; c <= rollMax[f]; c++) same += dp[f][c];
                for (int c = 1; c <= rollMax[f]; c++)
                    nxt[f][c] = c == 1 ? ((total - same) % MOD + MOD) % MOD : dp[f][c - 1];
            }
            dp = nxt;
        }
        long ans = 0;
        for (int f = 0; f < 6; f++)
            for (int c = 1; c <= rollMax[f]; c++) ans = (ans + dp[f][c]) % MOD;
        return (int) ans;
    }
}

int dieSimulator(int n, vector<int>& rollMax) {
    const long long MOD = 1000000007LL;
    vector<vector<long long>> dp(6);
    for (int f = 0; f < 6; f++) { dp[f].assign(rollMax[f] + 1, 0); dp[f][1] = 1; }
    for (int r = 1; r < n; r++) {
        vector<vector<long long>> nxt(6);
        long long total = 0;
        for (int g = 0; g < 6; g++)
            for (int c = 1; c <= rollMax[g]; c++) total += dp[g][c];
        total %= MOD;
        for (int f = 0; f < 6; f++) {
            nxt[f].assign(rollMax[f] + 1, 0);
            long long same = 0;
            for (int c = 1; c <= rollMax[f]; c++) same += dp[f][c];
            for (int c = 1; c <= rollMax[f]; c++)
                nxt[f][c] = c == 1 ? ((total - same) % MOD + MOD) % MOD : dp[f][c - 1];
        }
        dp = nxt;
    }
    long long ans = 0;
    for (int f = 0; f < 6; f++)
        for (int c = 1; c <= rollMax[f]; c++) ans = (ans + dp[f][c]) % MOD;
    return (int) ans;
}

Explanation

We count valid roll sequences by remembering, for every partial sequence, two things: which face it ends on and how many times that face has repeated consecutively. That extra "streak" dimension is what lets us enforce each rollMax limit.

The state is dp[f][c] = number of sequences ending in face f with a current run of c equal faces. At the start (one roll) every face has a run of 1, so dp[f][1] = 1.

To add one more roll for face f: if the new roll starts a fresh run (c = 1), the previous roll must have been a different face, so we take total - same (all sequences minus those already ending in f). If it extends a run (c > 1), it simply shifts up from dp[f][c-1], and we never let c exceed rollMax[f].

Example: n = 2, rollMax = [1,1,2,2,2,3]. There are 6×6 = 36 pairs, but faces 1 and 2 may repeat at most once, so (1,1) and (2,2) are illegal. That removes 2 sequences, leaving 34.

Each roll updates a small table of six faces times their limits, so the cost grows linearly with n. All sums are taken modulo 10^9 + 7.

Time: O(n · 6 · max(rollMax)) Space: O(6 · max(rollMax))