Dice Roll Simulation

This problem asks to find the number of distinct sequences of dice rolls of length n, given constraints on the maximum consecutive rolls of each face (1 to 6). The constraints are provided in the rollMax array.

Approach:

Both solutions presented utilize dynamic programming principles, albeit with different implementations: memoization (top-down) and iterative (bottom-up). Both share the same core idea: breaking down the problem into smaller subproblems.

Solution 1: Memoization (Top-Down)

This approach uses recursion with a memoization table (f in the code) to store and reuse results of subproblems. The function dfs(i, j, x) calculates the number of distinct sequences:

• i: The current roll number (0-indexed).
• j: The value of the current roll (1 to 6).
• x: The number of consecutive times the value j has been rolled.

The base case is when i reaches n (all rolls completed), returning 1 (a valid sequence). The recursive step explores all possible values for the next roll k. If k differs from j, it resets the consecutive count x to 1. If k is the same as j, it only continues if x is within the allowed limit (rollMax[j-1]). The results are memoized to prevent redundant calculations.

Time and Space Complexity Analysis (Solution 1):

• Time Complexity: O(n * 6 * max(rollMax)). The recursion explores at most n rolls, 6 possible values for each roll, and up to the maximum consecutive rolls for each face.
• Space Complexity: O(n * 6 * max(rollMax)). This is due to the memoization table storing results of subproblems.

Solution 2: Dynamic Programming (Bottom-Up)

This approach iteratively builds a 3D DP table f[i][j][x], where:

• i: Roll number (1-indexed).
• j: Value of the roll (1 to 6).
• x: Consecutive rolls of value j.

The base case is f[1][j][1] = 1 for all j. The iterative part then fills the table: For each i, j, and x, it sums the contributions from previous rolls k. If k != j, the count is updated at f[i][k][1]. If k == j and x + 1 is within the limit, it's updated at f[i][j][x + 1].

Time and Space Complexity Analysis (Solution 2):

• Time Complexity: O(n * 6 * max(rollMax)). Similar to the memoization approach, it iterates through all possible states.
• Space Complexity: O(n * 6 * max(rollMax)). This is the size of the DP table.

Code Examples (Python):

Solution 1 (Memoization):

from functools import cache
 
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        mod = 10**9 + 7
 
        @cache
        def dfs(i, prev_roll, consecutive_count):
            if i == n:
                return 1
            ans = 0
            for curr_roll in range(1, 7):
                if curr_roll != prev_roll:
                    ans = (ans + dfs(i + 1, curr_roll, 1)) % mod
                elif consecutive_count < rollMax[curr_roll - 1]:
                    ans = (ans + dfs(i + 1, curr_roll, consecutive_count + 1)) % mod
            return ans
 
        return dfs(0, 0, 0)

Solution 2 (Dynamic Programming):

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        mod = 10**9 + 7
        dp = [[[0] * 16 for _ in range(7)] for _ in range(n + 1)]
        for j in range(1, 7):
            dp[1][j][1] = 1
 
        for i in range(2, n + 1):
            for j in range(1, 7):
                for x in range(1, rollMax[j - 1] + 1):
                    for k in range(1, 7):
                        if k != j:
                            dp[i][k][1] = (dp[i][k][1] + dp[i - 1][j][x]) % mod
                        elif x + 1 <= rollMax[j - 1]:
                            dp[i][j][x + 1] = (dp[i][j][x + 1] + dp[i - 1][j][x]) % mod
 
        ans = 0
        for j in range(1, 7):
            for x in range(1, rollMax[j - 1] + 1):
                ans = (ans + dp[n][j][x]) % mod
        return ans
 

Note: The code examples in other languages (Java, C++, Go) follow similar logic to the Python examples, adapting syntax and data structures as needed. The core DP/memoization strategy remains the same.