Dice Roll Simulation - Solution & Explanation

In this approach, we'll use a 3D dynamic programming (DP) array to keep track of the number of ways to have a valid sequence up to the i^th roll, ending with j as the last rolled number, with k consecutive rolls of j.

Our main DP state can be expressed as dp[i][j][k], where i represents the number of rolls, j represents the last face value, and k represents how many times this face value has been rolled consecutively.

For the transition, notice that if we want the current roll to be number j, we can extend a sequence ending with j k times using the face j again if k < rollMax[j-1]. If we use a different number instead, we reset k to 1 for a new number.

This Python solution uses a 3D DP array to keep track of valid rolls, as discussed. The final result is computed by summing up all valid sequences of length n for any face and consecutive counts allowed by rollMax.

Instead of a 3D array, this approach uses a 2D array, where dp[i][j] represents the number of sequences of length i that end with number j, without specifically tracking consecutive count. This approach is less memory intensive but requires careful bookkeeping of the last rolled sequences according to constraints.

This Java solution employs a 2D DP array to find valid sequences. With each roll, it updates the sum of possibilities by calculating across different faces.

We can design a function dfs(i, j, x) to represent the number of schemes starting from the i-th dice roll, with the current dice roll being j, and the number of consecutive times j is rolled being x. The range of j is [1, 6], and the range of x is [1, rollMax[j - 1]]. The answer is dfs(0, 0, 0).

The calculation process of the function dfs(i, j, x) is as follows:

• If i \ge n, it means that n dice have been rolled, return 1.
• Otherwise, we enumerate the number k rolled next time. If k \ne j, we can directly roll k, and the number of consecutive times j is rolled will be reset to 1, so the number of schemes is dfs(i + 1, k, 1). If k = j, we need to judge whether x is less than rollMax[j - 1]. If it is less, we can continue to roll j, and the number of consecutive times j is rolled will increase by 1, so the number of schemes is dfs(i + 1, j, x + 1). Finally, add all the scheme numbers to get the value of dfs(i, j, x). Note that the answer may be very large, so we need to take the modulus of 10^9 + 7.

During the process, we can use memoization search to avoid repeated calculations.

The time complexity is O(n times k^2 times M), and the space complexity is O(n times k times M). Here, k is the range of dice points, and M is the maximum number of times a certain point can be rolled consecutively.

We can change the memoization search in Solution 1 to dynamic programming.

Define f[i][j][x] as the number of schemes for the first i dice rolls, with the i-th dice roll being j, and the number of consecutive times j is rolled being x. Initially, f[1][j][1] = 1, where 1 leq j leq 6. The answer is:

$ sum_{j=1}^6 sum_{x=1}^{rollMax[j-1]} f[n][j][x]

We enumerate the last dice roll as j, and the number of consecutive times j is rolled as x. The current dice roll can be 1, 2, cdots, 6. If the current dice roll is k, there are two cases:

• If k neq j, we can directly roll k, and the number of consecutive times j is rolled will be reset to 1. Therefore, the number of schemes f[i][k][1] will increase by f[i-1][j][x].
• If k = j, we need to judge whether x+1 is less than or equal to rollMax[j-1]. If it is less than or equal to, we can continue to roll j, and the number of consecutive times j is rolled will increase by 1. Therefore, the number of schemes f[i][j][x+1] will increase by f[i-1][j][x].

The final answer is the sum of all f[n][j][x].

The time complexity is O(n times k^2 times M), and the space complexity is O(n times k times M). Here, k is the range of dice points, and M$ is the maximum number of times a certain point can be rolled consecutively.