This problem is clearly underrated as a “medium”. There are a few ways to solve this problem but I would consider all of them to be LeetCode Hard.
Approach 1: Recursion + Memoization
The first thing which comes into mind after seeing the problem is recursion. At each step, we can choose a number from 1-6 (if it is valid as we’ll see), keep track of the previous number chosen and track of the length of this consecutive previous number. For example, if we roll the dice and get 1,2,5,3,3 then the next recursion state will have previous = 3, curLen = 2. If the curLen of a number becomes equal to the rollMax of that number, we can choose it in that recursion call.
private int dfs(int dieLeft, int[] rollMax, int last, int curlen){
if(dieLeft == 0) return 1;
int ans = 0;
for(int i=0; i<6; i++){
if(i == last && curlen == rollMax[i]) continue;
ans = (ans + dfs(dieLeft - 1, rollMax, i, i == last ? curlen + 1 : 1)) % M;
}
return ans;
}
This will give TLE so we somehow have to add memoization to this approach. Let’s identify the state variables of the recursion: number of rolls left (dieLeft), last number rolled (last) and length of last number rolled (curlen). We’ll simply use a 3D array to store this!
int[][][] dp = new int[5000][6][16];
final int M = 1000000007;
public int dieSimulator(int n, int[] rollMax) {
return dfs(n, rollMax, -1, 0);
}
private int dfs(int dieLeft, int[] rollMax, int last, int curlen){
if(dieLeft == 0) return 1;
if(last >= 0 && dp[dieLeft][last][curlen] > 0) return dp[dieLeft][last][curlen];
int ans = 0;
for(int i=0; i<6; i++){
if(i == last && curlen == rollMax[i]) continue;
ans = (ans + dfs(dieLeft - 1, rollMax, i, i == last ? curlen + 1 : 1)) % M;
}
if(last >= 0) dp[dieLeft][last][curlen] = ans;
return ans;
}
Approach 2: Dynamic Programming O(n*max(rollMax))
This is one of the simple approaches of dynamic programming for this question. Consider a 2D DP array dp[i][j] which denotes the number of ways to get number j at the i-th roll. Clearly, the array will be of size n*6 (We are considering the numbers on the die to be 0-indexed, i.e, 0, 1, 2, 3, 4, and 5). Let’s understand the recurrence in this bottom-up DP approach:
Let's say rollMax[J] = k. At the i-th iteration, we can have the following possible cases:
- ...*J (1 J)
- ..*JJ (2 consecutive J)
- .*JJJ (3 consecutive J)
- *JJJJ (K consecutive J)
Here, dot (.) denotes a number we don't care about and asterisk (*) denotes a number other than J.
Clearly, the number of ways to end up with J at the i-th iteration is dp[i-1][*] + dp[i-2][*] + dp[i-3][*] + ... + dp[i-k][*]
Now, define sum[i] as dp[i][0]+dp[i][1]+...+dp[i][5]. To calculate dp[i][*], we can simply do sum[i] - dp[i][J].
So number of ways to end up with J at the i-th iteration is (sum[i-1]-dp[i-1][J])+(sum[i-2]-dp[i-2][J])+...+(sum[i-k]-dp[i-k][J])
class Solution {
public:
int dieSimulator(int n, vector<int>& rollMax) {
long p = 1e9 + 7;
vector<vector<long>> dp(n+1, vector<long>(6, 0));
vector<long> sum(n+1, 0);
sum[0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 6; ++j) {
for (int k = 1; k <= rollMax[j] && i - k >= 0; ++k)
dp[i][j] = (dp[i][j] + sum[i-k] - dp[i-k][j] + p) % p;
sum[i] = (sum[i] + dp[i][j]) % p;
}
}
return sum[n];
}
};
Time complexity: O(n*max(rollMax))
Space complexity: O(n)
Note that we do not consider “6” in time and space complexity.
Approach 3: Dynamic Programming O(n)
This approach is similar to one above but still a tad bit more difficult to think according to me. dp[i][j] is the same as above, i.e., it denotes the number of ways to get number j at the i-th roll. Again assume, rollMax[J] = k. Let’s find out the number of ways to have J at the i-th iteration:
Consider the outcomes to be "axx..xxJ" where number of consecutive x = k. 'x' and 'a' denote some number.
Now, since we are rolling out J in this iteration. We want to exclude the case where x=J, i.e., aJJ..JJJ because in this case we will have (k+1) consecutive Js. How many number of such cases would be there?
When value of 'a' is anything but J, we can have value of k-consecutive 'x' to be equal to J. So the number of such cases would be number of cases where value of 'a' is not J. Hence, dp[i][J] = sum[i-1] - (sum[i-k-1] - dp[i-k-1][J])
class Solution {
public int dieSimulator(int n, int[] rollMax) {
long divisor = (long)Math.pow(10, 9) + 7;
long[][] dp = new long[n][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 - rollMax[j] < 0) {
sum = (sum + dp[i][j]) % divisor;
}
else {
if(i - rollMax[j] - 1 >= 0) dp[i][j] = (dp[i][j] - (dp[i - rollMax[j] - 1][6] - dp[i - rollMax[j] - 1][j])) % divisor + divisor;
else dp[i][j] = (dp[i][j] - 1) % divisor;
sum = (sum + dp[i][j]) % divisor;
}
}
dp[i][6] = sum;
}
return (int)(dp[n - 1][6]);
}
}
Time complexity: O(n)
Space complexity: O(1)