Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1223.html

1223. Dice Roll Simulation (Medium)

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.

Two sequences are considered different if at least one element differs from each other. Since the answer may be too large, return it modulo 10^9 + 7.

 

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

Related Topics:
Dynamic Programming

Solution 1. DP

Let dp[i][j] be the number of distinct sequences ending with j obtained using i rolles.

dp[1][j] = 1       1 <= j <= 6

Ignoring the rollMax, we have dp[i][j] = sum( dp[i-1][k] | 1 <= k <= 6 ).

If we pick j at i roll, we need to exclude the cases where there are already rollMax[j] j numbers right in front of ith roll.

The number of such cases is dp[i-rollMax[j]-1][k] where 1 <= k <= 6 and k != j.

// OJ: https://leetcode.com/problems/dice-roll-simulation/
// Time: O(N)
// Space: O(N)
// Ref: https://leetcode.com/problems/dice-roll-simulation/discuss/403756/Java-Share-my-DP-solution
class Solution {
public:
    int dieSimulator(int n, vector<int>& A) {
        long mod = 1e9+7;
        vector<vector<long>> dp(n, vector<long>(7));
        for (int i = 0; i < 6; ++i) dp[0][i] = 1;
        dp[0][6] = 6;
        for (int i = 1; i < n; ++i) {
            long sum = 0;
            for (int j = 0; j < 6; ++j) {
                dp[i][j] = dp[i - 1][6];
                if (i < A[j]) sum = (sum + dp[i][j]) % mod;
                else {
                    if (i - A[j] - 1 >= 0) dp[i][j] = (dp[i][j] - (dp[i - A[j] - 1][6] - dp[i - A[j] - 1][j]) + mod) % mod;
                    else dp[i][j] = (dp[i][j] - 1) % mod;
                    sum = (sum + dp[i][j]) % mod;
                }
            }
            dp[i][6] = sum;
        }
        return dp[n - 1][6];
    }
};
  • class Solution {
        public int dieSimulator(int n, int[] rollMax) {
            final int MODULO = 1000000007;
            int[][][] dp = new int[n][6][15];
            for (int i = 0; i < 6; i++)
                dp[0][i][0] = 1;
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < 6; j++) {
                    for (int k = 0; k < 6; k++) {
                        if (k == j)
                            continue;
                        for (int m = 0; m < 15; m++)
                            dp[i][j][0] = (dp[i][j][0] + dp[i - 1][k][m]) % MODULO;
                    }
                    int max = rollMax[j];
                    for (int k = 1; k < max; k++)
                        dp[i][j][k] = dp[i - 1][j][k - 1];
                }
            }
            int sum = 0;
            for (int i = 0; i < 6; i++) {
                for (int j = 0; j < 15; j++)
                    sum = (sum + dp[n - 1][i][j]) % MODULO;
            }
            return sum;
        }
    }
    
    ############
    
    class Solution {
        private Integer[][][] f;
        private int[] rollMax;
    
        public int dieSimulator(int n, int[] rollMax) {
            f = new Integer[n][7][16];
            this.rollMax = rollMax;
            return dfs(0, 0, 0);
        }
    
        private int dfs(int i, int j, int x) {
            if (i >= f.length) {
                return 1;
            }
            if (f[i][j][x] != null) {
                return f[i][j][x];
            }
            long ans = 0;
            for (int k = 1; k <= 6; ++k) {
                if (k != j) {
                    ans += dfs(i + 1, k, 1);
                } else if (x < rollMax[j - 1]) {
                    ans += dfs(i + 1, j, x + 1);
                }
            }
            ans %= 1000000007;
            return f[i][j][x] = (int) ans;
        }
    }
    
  • // OJ: https://leetcode.com/problems/dice-roll-simulation/
    // Time: O(N)
    // Space: O(N)
    // Ref: https://leetcode.com/problems/dice-roll-simulation/discuss/403756/Java-Share-my-DP-solution
    class Solution {
    public:
        int dieSimulator(int n, vector<int>& A) {
            long mod = 1e9+7;
            vector<vector<long>> dp(n, vector<long>(7));
            for (int i = 0; i < 6; ++i) dp[0][i] = 1;
            dp[0][6] = 6;
            for (int i = 1; i < n; ++i) {
                long sum = 0;
                for (int j = 0; j < 6; ++j) {
                    dp[i][j] = dp[i - 1][6];
                    if (i < A[j]) sum = (sum + dp[i][j]) % mod;
                    else {
                        if (i - A[j] - 1 >= 0) dp[i][j] = (dp[i][j] - (dp[i - A[j] - 1][6] - dp[i - A[j] - 1][j]) + mod) % mod;
                        else dp[i][j] = (dp[i][j] - 1) % mod;
                        sum = (sum + dp[i][j]) % mod;
                    }
                }
                dp[i][6] = sum;
            }
            return dp[n - 1][6];
        }
    };
    
  • class Solution:
        def dieSimulator(self, n: int, rollMax: List[int]) -> int:
            @cache
            def dfs(i, j, x):
                if i >= n:
                    return 1
                ans = 0
                for k in range(1, 7):
                    if k != j:
                        ans += dfs(i + 1, k, 1)
                    elif x < rollMax[j - 1]:
                        ans += dfs(i + 1, j, x + 1)
                return ans % (10 ** 9 + 7)
    
            return dfs(0, 0, 0)
    
    
    
  • func dieSimulator(n int, rollMax []int) int {
    	f := make([][7][16]int, n)
    	const mod = 1e9 + 7
    	var dfs func(i, j, x int) int
    	dfs = func(i, j, x int) int {
    		if i >= n {
    			return 1
    		}
    		if f[i][j][x] != 0 {
    			return f[i][j][x]
    		}
    		ans := 0
    		for k := 1; k <= 6; k++ {
    			if k != j {
    				ans += dfs(i+1, k, 1)
    			} else if x < rollMax[j-1] {
    				ans += dfs(i+1, j, x+1)
    			}
    		}
    		f[i][j][x] = ans % mod
    		return f[i][j][x]
    	}
    	return dfs(0, 0, 0)
    }
    

All Problems

All Solutions