1223. Dice Roll Simulation

Description

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.

 

Example 1:

Input: n = 2, rollMax = [1,1,2,2,2,3]
Output: 34
Explanation: There will be 2 rolls of die, if there are no constraints on the die, there are 6 * 6 = 36 possible combinations. In this case, looking at rollMax array, the numbers 1 and 2 appear at most once consecutively, therefore sequences (1,1) and (2,2) cannot occur, so the final answer is 36-2 = 34.

Example 2:

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

Example 3:

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

 

Constraints:

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

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(n*Max(rollMax[i]))
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number} n
 * @param {number[]} rollMax
 * @return {number}
 */
const dieSimulator = function (n, rollMax) {
  const MODULO = 10 ** 9 + 7;
  const dp = Array.from({ length: n + 1 }, () => Array.from({ length: 6 }, () => 0));
  const sum = Array.from({ length: n + 1 }, () => 0);

  sum[0] = 1;

  for (let roll = 1; roll <= n; roll++) {
    for (let die = 0; die < 6; die++) {
      for (let continuous = 1; continuous <= rollMax[die]; continuous++) {
        if (continuous > roll) continue;
        const times = (sum[roll - continuous] - dp[roll - continuous][die] + MODULO) % MODULO;

        dp[roll][die] = (dp[roll][die] + times) % MODULO;
      }
      sum[roll] = (sum[roll] + dp[roll][die]) % MODULO;
    }
  }

  return sum[n];
};