【Leetcode】1223. Dice Roll Simulation

题目地址：

https://leetcode.com/problems/dice-roll-simulation/

给定一个六面筛子，再给定一个长$6$的数组$v$，数字$x$可以连续出现的次数为$v[x-1]$。$\forall x,v[x]\le 15$。问这个筛子扔出的长$n$的不同序列有多少个。

设$f[l][x][k]$为长$l$的且以$k$个$x$结尾的不同序列有多少个。这个题写成将$f[l]$累加到$f[l+1]$比较好写，当然要略过不合法的情形。直接递推一遍即可。代码如下：

class Solution {
 public:
  int dieSimulator(int n, vector<int>& v) {
    const int MOD = 1e9 + 7;
    int f[n + 1][6][16];
    memset(f, 0, sizeof f);
    for (int i = 0; i < 6; i++) f[1][i][1] = 1;
    for (int i = 1; i < n; i++)
      // 枚举长i的序列最后一个数字
      for (int x = 0; x < 6; x++)
        for (int k = 1; k <= v[x]; k++)
          // 枚举下面要接上哪个数字
          for (int y = 0; y < 6; y++) {
            int len = 1;
            // 如果接上的数字相同，则要判断是否触发条件
            if (x == y) {
              len = k + 1;
              if (len > v[x]) continue;
            }
            f[i + 1][y][len] = (f[i + 1][y][len] + f[i][x][k]) % MOD;
          }

    int res = 0;
    for (int i = 0; i < 6; i++)
      for (int j = 1; j <= v[i]; j++) res = (res + f[n][i][j]) % MOD;
    return res;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

时空复杂度$O(n)$。