算法动态规划

自动机DP

字数统计: 1.3k字   |   阅读时长: 6分
,

1220. 统计元音字母序列的数目

问题

给你一个整数 n，请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串：

字符串中的每个字符都应当是小写元音字母（’a’, ‘e’, ‘i’, ‘o’, ‘u’）

  • 每个元音 ‘a’ 后面都只能跟着 ‘e’
  • 每个元音 ‘e’ 后面只能跟着 ‘a’ 或者是 ‘i’
  • 每个元音 ‘i’ 后面 不能 再跟着另一个 ‘i’
  • 每个元音 ‘o’ 后面只能跟着 ‘i’ 或者是 ‘u’
  • 每个元音 ‘u’ 后面只能跟着 ‘a’

由于答案可能会很大，所以请你返回 模 10^9 + 7 之后的结果。

分析

(1) 设计自动机

画状态转换图 D

fsm.jpg

(2) 在自动机上动态规划

1
2
3
4
5
dp[x][k] := 当前状态为 x，往前走 k 次，可形成的串数量

初始化： dp[x][0] = 1
答案： sum(dp[rollStart[0~5]][n-1])
转移： dp[x][k] = sum(dp[D[x][y]][k - 1]), y 满足 D[x][y] == 1

代码

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
29
30
31
32
33
class Solution {
public:
    int countVowelPermutation(int n) {
        D = vector<vector<int>>{
            {0, 1, 0, 0, 0},
            {1, 0, 1, 0, 0},
            {1, 1, 0, 1, 1},
            {0, 0, 1, 0, 1},
            {1, 0, 0, 0, 0}
        };
        vector<vector<int>> dp(5, vector<int>(n + 1));
        for(int x = 0; x < 5; ++x)
            dp[x][1] = 1;
        for(int k = 2; k <= n; ++k)
        {
            for(int x = 0; x < 5; ++x)
            {
                for(int y = 0; y < 5; ++y)
                    if(D[x][y] == 1)
                        dp[x][k] = (dp[x][k] + (ll)dp[y][k - 1]) % MOD;
            }
        }
        int ans = 0;
        for(int i = 0; i < 5; ++i)
            ans = (ans + (ll)dp[i][n]) % MOD;
        return ans;
    }

private:
    using ll = long long;
    const int MOD = 1e9 + 7;
    vector<vector<int>> D;
};

1641. 统计字典序元音字符串的数目

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
class Solution {
public:
    int countVowelStrings(int n) {
        vector<vector<int>> D = {
            {1, 1, 1, 1, 1},
            {0, 1, 1, 1, 1},
            {0, 0, 1, 1, 1},
            {0, 0, 0, 1, 1},
            {0, 0, 0, 0, 1}
        };
        vector<vector<int>> dp(5, vector<int>(n + 1));
        for(int s = 0; s < 5; ++s)
            dp[s][1] = 1;
        for(int i = 2; i <= n; ++i)
        {
            for(int v = 0; v < 5; ++v)
                for(int u = 0; u < 5; ++u)
                {
                    if(D[u][v] == 1)
                        dp[v][i] += dp[u][i - 1];
                }
        }
        int ans = 0;
        for(int s = 0; s < 5; ++s)
            ans += dp[s][n];
        return ans;
    }
};

1223. 掷骰子模拟

问题

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

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

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

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

分析

(1) 设计自动机

画状态转换图 D，记 D 中的状态编号 0 <= x < N

1
2
状态编号 x = rollStart[k] + c 为连续第 c 次点数 k (`0 <= c < rollMax[k]`, `0 <= k < 6`)
rollStart[k] := 第 0 次点数 k 在 D 中的编号

对于图中的两个状态 x, y。

  • 如果它们属于同一点数，则 y = x + 1 时，D[x][y] = 1
  • 如果它们属于不同点数，则 y 为其对应点数第 0 次出现时，D[x][y] = 1

以 rollMax = {2, 4, 2, 1, 3, 2} 为例
首先求出 N = 14, rollStart = {0, 2, 6, 8, 9, 12}
然后画 N * N 的状态转换图，将符合要求的点 (x, y) 标为 D[x][y] = 1，表示状态 x 可以到状态 y


(2) 在自动机上动态规划

1
2
3
4
5
dp[x][i] := 当前状态为 x，再抛 i 次，可形成的方案数

初始化： dp[x][0] = 1
答案： sum(dp[rollStart[0~5]][n-1])
转移： dp[x][i] = sum(dp[y][i]), y 满足 D[x][y] == 1

代码

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    int dieSimulator(int n, vector<int>& rollMax) {
        using ll = long long;
        const int MOD = 1e9 + 7;

        int N = 0;
        for(int i: rollMax) N += i;
        vector<vector<int>> D(N, vector<int>(N, 0));
        // rollStart[i] := 点数 i 在 D 中的起始下标
        // 终止下标为 rollStart[i] + rollMax[i] - 1
        vector<int> rollStart(6);
        for(int i = 1; i < 6; ++i)
            rollStart[i] = rollStart[i - 1] + rollMax[i - 1];
        for(int i = 0; i < 6; ++i)
        {
            for(int j = 0; j < 6; ++j)
            {
                if(i == j)
                {
                    int left = rollStart[i];
                    int len = rollMax[i];
                    for(int x = left; x < left + len; ++x)
                    {
                        for(int y = left; y < left + len; ++y)
                        {
                            if(x + 1 == y)
                                D[x][y] = 1;
                        }
                    }
                }
                else
                {
                    int lefti = rollStart[i];
                    int leni = rollMax[i];
                    int leftj = rollStart[j];
                    for(int x = lefti; x < lefti + leni; ++x)
                        D[x][leftj] = 1;
                }
            }
        }

        vector<vector<int>> dp(N, vector<int>(n));
        for(int x = 0; x < N; ++x)
            dp[x][0] = 1;
        for(int i = 1; i < n; ++i)
            for(int x = 0; x < N; ++x)
            {
                for(int y = 0; y < N; ++y)
                {
                    if(D[x][y] == 1)
                        dp[x][i] = (dp[x][i] + (ll)dp[y][i - 1]) % MOD;
                }
            }

        int ans = 0;
        for(int k = 0; k < 6; ++k)
            ans = (ans + dp[rollStart[k]][n - 1]) % MOD;
        return ans;
    }
};
Share