# 1223.掷骰子模拟 (Hard)

## 问题描述
[1223. 掷骰子模拟 (Hard)](https://leetcode.cn/problems/dice-roll-simulation/)

有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。

不过我们在使用它时有个约束，就是使得投掷骰子时， **连续** 掷出数字 `i` 的次数不能超过
`rollMax[i]`（ `i` 从 1 开始编号）。

现在，给你一个整数数组 `rollMax` 和一个整数 `n`，请你来计算掷 `n` 次骰子可得到的不同点数序列的数量。

假如两个序列中至少存在一个元素不同，就认为这两个序列是不同的。由于答案可能很大，所以请返回 **模 `10^9 +
7`** 之后的结果。

**示例 1：**

```
输入：n = 2, rollMax = [1,1,2,2,2,3]
输出：34
解释：我们掷 2 次骰子，如果没有约束的话，共有 6 * 6 = 36 种可能的组合。但是根据 rollMax
数组，数字 1 和 2 最多连续出现一次，所以不会出现序列 (1,1) 和 (2,2)。因此，最终答案是 36-2 =
34。

```

**示例 2：**

```
输入：n = 2, rollMax = [1,1,1,1,1,1]
输出：30

```

**示例 3：**

```
输入：n = 3, rollMax = [1,1,1,2,2,3]
输出：181

```

**提示：**

- `1 <= n <= 5000`
- `rollMax.length == 6`
- `1 <= rollMax[i] <= 15`

## 解题思路
### 动态规划
这一题是很明显的动态规划思路，状态定义很好想，状态转移方程也不难确定：

记`dp[i][j]`为掷`i`次骰子，最后一次结果为`j + 1`的可能的组合，要求的答案即`dp[n][0] + ... + dp[n][5]`，显然，我们只需排除最后`rollMax[j] + 1`次都是`j`的情况；

状态转移方程为：
`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]$

### 记忆化搜索
这里我们从第`n`次向第一次倒着考虑，那么我们要关注的几个变量：
- 当前投掷骰子的次数`idx`；
- **当前投掷的骰子数字**减一，记为`last_num`；
- 当前数字往后的最大连续数量，记为`max_len`，例如$623166$，考虑`idx = 5`，那么最大连续数量就是$2$，这里的`max_len`要分等于`rollMax[last_num]`和小于`rollMax[last_num]`的情况来讨论，小于则可以继续选`last_num`，内层递归的`max_len`为`max_len + 1`；否则必须选其他的数，同时内层递归的`max_len`置1；

当前递归的结果应该取下一层递归的结果之和；

边界条件，当`idx == 0`时，应该`return 1;`

`cache`数组的三个维度即`idx`，`last_num`，`max_len`，其中`max_len <= 15`，所以`cache`数组为`vector<vector<vector<long>>> cache(n + 1, vector<vector<long>>(16, vector<long>(6, -1)));`

## 代码
### 动态规划
```cpp
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;
    }
};
```

### 记忆化搜索
```cpp
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);
    }
};
```