Dice roll simulation

Array Dynamic Programming

50.7% acceptance

Feb 25, 2026

997

198

A die simulator generates a random number from 1 to 6 for each roll. You introduced a constraint to the generator such that it cannot roll the number i more than rollMax[i] (1-indexed) consecutive times. Given an array of integers rollMax and an integer n, return the number of distinct sequences that can be obtained with exact n rolls. Since the answer may be too large, return it modulo 109 + 7. Two sequences are considered different if at least one element differs from each other.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn die_simulator(n: i32, roll_max: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = n as usize;
    let max_consec = 15usize;
    // dp[face][consec] = count
    // face: 0..5, consec: 1..=rollMax[face]
    let mut dp = vec![vec![0i64; max_consec + 1]; 6];
    for f in 0..6 {
      dp[f][1] = 1;
    }

    for _ in 1..n {
      let mut ndp = vec![vec![0i64; max_consec + 1]; 6];
      for f in 0..6 {
        for k in 1..=roll_max[f] as usize {
          if dp[f][k] == 0 { continue; }
          // Roll a different face
          for nf in 0..6 {
            if nf != f {
              ndp[nf][1] = (ndp[nf][1] + dp[f][k]) % MOD;
            }
          }
          // Roll same face
          if k < roll_max[f] as usize {
            ndp[f][k + 1] = (ndp[f][k + 1] + dp[f][k]) % MOD;
          }
        }
      }
      dp = ndp;
    }

    let mut ans = 0i64;
    for f in 0..6 {
      for k in 1..=roll_max[f] as usize {
        ans = (ans + dp[f][k]) % MOD;
      }
    }
    ans as i32
  }
}