LeetCode 1223: Dice Roll Simulation Solution
Master LeetCode problem 1223 (Dice Roll Simulation), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
1223. Dice Roll Simulation
Problem Explanation
Explanation
To solve this problem, we can use dynamic programming. We define a 3-dimensional dp array where dp[i][j][k] represents the number of distinct sequences ending with j repeated k times after i rolls. We can then iteratively calculate the number of valid sequences based on the constraints given in the problem.
At each step, we iterate over the previous state of the dp array and update the current state based on the constraints. We need to consider the cases where the current number is the same as the previous number and when it is different.
The final result will be the sum of all valid sequences in the dp array for a total of n rolls.
Time Complexity
The time complexity of this solution is O(n * 6 * 15 * 6), which simplifies to O(n).
Space Complexity
The space complexity is O(n * 6 * 15).
Solution Code
class Solution {
public int dieSimulator(int n, int[] rollMax) {
int MOD = 1000000007;
int[][][] dp = new int[n + 1][6][16];
for (int i = 0; i < 6; i++) {
dp[1][i][1] = 1;
}
for (int i = 2; i <= n; i++) {
for (int j = 0; j < 6; j++) {
for (int k = 1; k <= 15; k++) {
for (int l = 0; l < 6; l++) {
if (l != j) {
dp[i][j][1] = (dp[i][j][1] + dp[i - 1][l][k]) % MOD;
} else {
if (k < rollMax[j]) {
dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i - 1][l][k]) % MOD;
}
}
}
}
}
}
int total = 0;
for (int j = 0; j < 6; j++) {
for (int k = 1; k <= 15; k++) {
total = (total + dp[n][j][k]) % MOD;
}
}
return total;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 1223 (Dice Roll Simulation)?
This page provides optimized solutions for LeetCode problem 1223 (Dice Roll Simulation) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 1223 (Dice Roll Simulation)?
The time complexity for LeetCode 1223 (Dice Roll Simulation) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 1223 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1223 in Java, C++, or Python.