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 <= 5000rollMax.length == 61 <= 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) }