1223.Dice Roll Simulation (Hard)

Description Link to heading

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. Since the answer may be too large, return it modulo 10⁹ + 7.

Two sequences are considered different if at least one element differs from each other.

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

Solution Link to heading

DP Link to heading

This problem is obviously a problem of dynamic programming.

We denote dp[i][j] as the number of distinct sequences after rolling i times dice and the result of last rolling is j + 1. Obviously, we only need remove the case that last rollMax[j] + 1 rolls are all j.

The state transition equation is: if i <= rollMax[j]: $dp[i][j] = \sum\limits_{k = 0}^{5} dp[i - 1][k]$ else if i == rollMax[j] + 1: $dp[i][j] = \sum\limits_{k = 0}^{5} dp[i - 1][k] - 1$ else: $dp[i][j] = \sum\limits_{k = 0}^{5}dp[i - 1][k] - \sum\limits_{k = 0, k\neq j}^{5}dp[i - rollMax[j] - 1][j]$

memorized search Link to heading

Here we consider it backwards from the nth time towards the first, then we have several variables to focus on.

idx, the number of dice currently thrown.
the number of dice currently thrown minus one, noted as last_num.
The maximum number of consecutive numbers after the current number, noted as max_len, for example, $623166$, consider idx = 5, then the maximum number of consecutive is $2$.

Here max_len should be divided into equal to rollMax[last_num] and less than rollMax[last_num] to discuss the case, less than then you can continue to choose last_num, and the max_len of the inner recursion is max_len + 1; otherwise, you must choose another number, and the max_len of the inner recursion is set to 1.

The result of the current recursion should be taken as the sum of the results of the inner recursion.

Boundary condition, when idx == 0, should return 1;

The three dimensions of the cache array i.e. idx, last_num, max_len, where max_len <= 15, so the cache array is vector<vector<vector<long>>> cache(n + 1, vector<vector<long>>( 16, vector<vector<long>(6, -1)));

Code Link to heading

DP Link to heading

class Solution {
  public:
    int dieSimulator(int n, vector<int> &rollMax) {
        int mod = 1000000007;
        if (n == 1) return 6;
        vector<vector<int>> dp(n + 1, vector<int>(6, 0));
        for (int i = 0; i < 6; i++) {
            dp[0][i] = 1;
            dp[1][i] = 1;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < 6; j++) {
                if (i <= rollMax[j]) {
                    dp[i][j] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][4] + dp[i - 1][5]) % mod;
                } else if (i == rollMax[j] + 1) {
                    int tmp_sum = 0;
                    for (int k = 0; k < 6; k++) {
                        tmp_sum = (tmp_sum + dp[i - 1][k]) % mod;
                    }
                    dp[i][j] = (tmp_sum - 1) % mod;
                } else {
                    int tmp_sum = 0;
                    int tmp_minus = 0;
                    for (int k = 0; k < 6; k++) {
                        tmp_sum = (tmp_sum + dp[i - 1][k]) % mod;
                        if (k == j) {
                            continue;
                        }
                        tmp_minus = (tmp_minus + dp[i - rollMax[j] - 1][k]) % mod;
                    }
                    dp[i][j] = (tmp_sum - tmp_minus + mod) % mod;
                }
            }
        }
        int res = 0;
        for (int j = 0; j < 6; j++) {
            res = (res + dp[n][j]) % mod;
        }
        return res;
    }
};

memorized search Link to heading

class Solution {
  public:
    long dfs(int idx, vector<int> &rollMax, int max_len, int last_num, vector<vector<vector<long>>> &cache, int mod) {
        if (idx == 0) {
            return 1;
        }
        if (cache[idx][max_len][last_num] >= 0) {
            return cache[idx][max_len][last_num] % mod;
        }
        long res = 0;
        if (max_len < rollMax[last_num]) {
            for (int i = 0; i < 6; ++i) {
                if (i == last_num) {
                    res += dfs(idx - 1, rollMax, max_len + 1, i, cache, mod);
                    res %= mod;
                } else {
                    res += dfs(idx - 1, rollMax, 1, i, cache, mod);
                    res %= mod;
                }
            }
        } else {
            for (int i = 0; i < 6; ++i) {
                if (i != last_num) {
                    res += dfs(idx - 1, rollMax, 1, i, cache, mod);
                    res %= mod;
                }
            }
        }
        cache[idx][max_len][last_num] = res % mod;
        return cache[idx][max_len][last_num];
    }
    int dieSimulator(int n, vector<int> &rollMax) {
        vector<vector<vector<long>>> cache(n + 1, vector<vector<long>>(16, vector<long>(6, -1)));
        int mod = 1000000007;
        return dfs(n, rollMax, 0, 6, cache, mod);
    }
};