- LeetCode1220：统计元音字母序列的数目
- 时间：2022-01-17
- 力扣难度：Hard
- 个人难度：Hard
- 数据结构：字符串
- 算法：状态机、动态规划、DFS、矩阵快速幂
LeetCode1220.统计元音字母序列的数目：「状态DP」&「矩阵快速幂」
1. 题目描述
题目：原题链接
- 给你一个整数 n，请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符
- 字符串中的每个字符都应当是小写元音字母（’a’, ‘e’, ‘i’, ‘o’, ‘u’）
- 每个元音 ‘a’ 后面都只能跟着 ‘e’
- 每个元音 ‘e’ 后面只能跟着 ‘a’ 或者是 ‘i’
- 每个元音 ‘i’ 后面 不能 再跟着另一个 ‘i’
- 每个元音 ‘o’ 后面只能跟着 ‘i’ 或者是 ‘u’
- 每个元音 ‘u’ 后面只能跟着 ‘a’
- 由于答案可能会很大，所以请你返回 模 10^9 + 7 之后的结果。
- 给你一个整数 n，请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符
输入输出规范：
- 输入：整数 n ：
1 <= n <= 2 * 10^4 - 输出：可以组成的长度为 n 的元音字母序列的个数
- 输入：整数 n ：
输入输出示例
- 输入：n = 2
- 输出：10
- 解释：所有可能的字符串分别是：”ae”, “ea”, “ei”, “ia”, “ie”, “io”, “iu”, “oi”, “ou” 和 “ua”。
2. 方法一：状态机DP
思路：状态机 & 动态规划
- 首先，本题给定了明确的规则，且只有五个元音字母，属于有限种状态，这种类型的题目一般可以考虑通过状态机来描述变化的过程
- 状态机主要是用来表示目标元素变化过程，比如我们经常使用一个布尔型的变量来表示一个问题的二元状态
- 对于本题而言，首先要确定状态的个数以及变化的规律，分析题干后可以得出
- a 的前面只能是：e、i、u
- e 的前面只能是：a、i
- i 的前面只能是：e、o
- o 的前面只能是：i
- u 的前面只能是：i、o
- 可以发现，每个字母前面的可选字母都是确定的，这里称为前置字母，且每个状态都与前一个状态相关，所以使用动态规划来解决
- 我们将状态定义为以某个字母结尾的字符串的数量，那么状态为五个
- 当我们求解一个以某字母结尾的长度为 n 的元音序列的个数时，由于前置字母确定，所以就相当于以其前置字母结尾的长度为 n-1 的序列的个数之和，这就可以通过逐个递推得到最终结果
- 注意：为了避免超出范围，要每一次都对数量进行取余操作
方式一：二维DP
分析：首先最容易想到的是二维DP，DP数组中同时包含长度和结尾字母的信息
DP三要素
dp[i][j]：表示以 j 字符结尾的长度为 i 的字符串的个数，j 对应五个元音字母- 边界条件：
dp[1][j]初始化为 1 - 状态转移方程：不同状态下转移方程不同，用 $j_k$ 表示 j 的前置字母$dp[i][j] = \sum_{}dp[i - 1][j_K]$
- 最终符合的字符串个数：$\sum_{j = 0}^{4}dp[n][j]$
题解：二维DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21// 方法一 ： 状态机、动态规划 二维DP
public int countVowelPermutation(int n) {
if (n == 1) return 5;
long[][] dp = new long[n + 1][5]; // 状态机DP数组：对应长度为 i 且五个元音字母结尾的字符串个数
for (int i = 0; i < dp[0].length; i++) {
dp[1][i] = 1;
}
long sum = 0L;
long mod = (long) (Math.pow(10, 9) + 7);
for (int i = 2; i < n + 1; i++) {
dp[i][0] = (dp[i - 1][1] + dp[i - 1][2] + dp[i-1][4]) % mod;
dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod;
dp[i][2] = (dp[i - 1][1] + dp[i - 1][3]) % mod;
dp[i][3] = dp[i - 1][2] % mod;
dp[i][4] = (dp[i - 1][2] + dp[i-1][3]) % mod;
}
for (int i = 0; i < 5; i++) {
sum = (sum + dp[n][i]) % mod;
}
return (int) sum;
}复杂度分析：n 是输入的整数
- 时间复杂度：$O(C*n)$，C 是元音字母的个数，本题为五个
- 空间复杂度：$O(C*n)$，二维DP数组
方式二：一维DP优化
分析
- 因为DP数组的当前状态只和上一个状态相关，所以可以将空间优化到一维，创建一个
dp[5]的数组即可 - 但是值得注意的是，由于前置字母不一定只有一个，即当前状态要用到上一个状态的多个
dp[i]，所以还要维护一个辅助数组help[5]来存储上次的结果
- 因为DP数组的当前状态只和上一个状态相关，所以可以将空间优化到一维，创建一个
DP三要素
dp[i]：表示以 i 字符结尾的字符串的个数，i 对应五个元音字母- 边界条件：
dp[i]初始化为 1 - 状态转移方程：不同状态下转移方程不同，用 $i_k$ 表示 i 的前置字母，有 $dp[i] = \sum_{}dp[i_k]$
- 最终符合的字符串个数：$\sum_{i = 0}^{4}dp[i]$
题解：一维DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24// 方法一 优化 ： 状态机、动态规划 一维DP
public int countVowelPermutation(int n) {
if (n == 1) return 5;
long[] dp = new long[5]; // 状态机DP数组：对应五个元音字母结尾的字符串个数
long[] help = new long[5]; // 辅助数组
Arrays.fill(dp, 1);
Arrays.fill(help, 1);
long sum = 0L;
long mod = (long) (Math.pow(10, 9) + 7);
for (int i = 1; i < n; i++) {
dp[0] = (help[1] + help[2] + help[4]) % mod;
dp[1] = (help[0] + help[2]) % mod;
dp[2] = (help[1] + help[3]) % mod;
dp[3] = help[2] % mod;
dp[4] = (help[2] + help[3]) % mod;
// help = Arrays.copyOf(dp, 5);
System.arraycopy(dp, 0, help, 0, 5);
}
// System.out.println(Arrays.toString(dp));
for (long count : dp) {
sum = (sum + count) % mod;
}
return (int) sum;
}复杂度分析：n 是输入的整数
- 时间复杂度：$O(C*n)$，C 是元音字母的个数，本题为五个
- 空间复杂度：$O(C)$，一维DP数组(两个)
3. 方法二：矩阵快速幂
思路：将状态机DP转换为矩阵计算
对于状态机DP问题而言，如果状态转移的过程可以表示为线性的叠加，就可以转换为矩阵计算来提高效率
为了求出
dp[n]，状态DP一般都需要遍历次，即线性的时间复杂度，而矩阵计算可以通过矩阵具有结合律的性质来将复杂度优化到对数级具体推导涉及到线性代数的知识，这里只作简单介绍，以本题为例，dp二维数组的递推过程可以等效为：
$$
f(n)=
\begin{gathered}
\begin{bmatrix}
0 & 1 & 1 & 0 & 1
\ 1 & 0 & 1 & 0 & 0
\ 0 & 1 & 0 & 1 & 0
\ 0 & 0 & 1 & 0 & 0
\ 0 & 0 & 1 & 1 & 0
\end{bmatrix}\end{gathered}*f(n-1)
\begin{gathered}
\begin{bmatrix}
0 & 1 & 1 & 0 & 1
\ 1 & 0 & 1 & 0 & 0
\ 0 & 1 & 0 & 1 & 0
\ 0 & 0 & 1 & 0 & 0
\ 0 & 0 & 1 & 1 & 0
\end{bmatrix}
\end{gathered}^{n-1}*f(1)
\ \
f(1)=\begin{bmatrix} 1 & 1 & 1 & 1 & 1 \end{bmatrix}
\ \
M=\begin{gathered}
\begin{bmatrix}
0 & 1 & 1 & 0 & 1
\ 1 & 0 & 1 & 0 & 0
\ 0 & 1 & 0 & 1 & 0
\ 0 & 0 & 1 & 0 & 0
\ 0 & 0 & 1 & 1 & 0
\end{bmatrix}
\end{gathered}
$$所以就将整个过程化简为求矩阵 M 的 n 次方问题，实际上就是矩阵乘法，结合快速幂算法：偶次幂时进行矩阵平方并将幂除2，奇次幂时进行矩阵与初始值相乘并赋值给初始值
注意：矩阵乘法要求前一个矩阵的列数等于后一个矩阵的行数，且结果的维度是行数与前一个矩阵行数相等，列数与后一个矩阵列数相等
题解
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// 方法三：矩阵快速幂
int MOD = (int) 1e9 + 7;
public int countVowelPermutation(int n) {
if (n == 1) return 5;
long[][] matrix = new long[][]{
{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},
};
long[][] first = new long[][]{
{1}, {1}, {1}, {1}, {1}
};
/*long[][] first = new long[matrix.length][matrix[0].length];
for (int i = 0; i < m; ++i) {
first[i][i] = 1;
}*/
// 快速幂
int x = n - 1;
while (x != 0) {
if ((x & 1) == 1) first = mul(matrix, first); // 奇次幂
matrix = mul(matrix, matrix); // 偶次幂
x >>= 1;
}
long sum = 0;
for (int i = 0; i < 5; i++) sum += first[i][0];
return (int) (sum % MOD);
}
private long[][] mul(long[][] matrixA, long[][] matrixB) {
// 第一个矩阵的行数，和第二个矩阵的列数
int row = matrixA.length, col = matrixB[0].length;
// 第一个矩阵的列数 = 第二个矩阵的行数(最内侧循环)
int len = matrixB.length;
long[][] res = new long[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
for (int k = 0; k < len; k++) {
res[i][j] += matrixA[i][k] * matrixB[k][j]; // 行和列相乘的和
res[i][j] %= MOD;
}
}
}
return res;
}复杂度分析：n 是输入的整数
- 时间复杂度：$O(C^3*logn)$，矩阵相乘的复杂度为$O(C^3)$，共相乘$O(logn)$次
- 空间复杂度：$O(C^2)$，维护的二维数组(矩阵)的空间
4. 方法三：DFS & 记忆化搜索
思路：深度优先搜索
- 除此之外，其实本题这种规定长度求个数的问题，也常用DFS来解决
- 具体而言，就是根据题目指定的规则，从前向后去搜索，找到了就对数量++
- 但是DFS在搜索的过程中复杂度较高，且包含很多重复搜索，需要通过记忆化，通过牺牲空间的方式优化，避免TLE超时
- DFS这种方法虽然效率不如状态机DP和矩阵快速幂，但是其思想简单，属于大家都能想到的方法
题解
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// 方法三 ： DFS + 记忆化搜索
char[] letter = new char[]{'a', 'e', 'i', 'o', 'u'};
// 记忆化搜索
Map<String, Long> map = new HashMap<>();
long mod = (long) (Math.pow(10, 9) + 7);
public int countVowelPermutation2(int n) {
if (n == 1) return 5;
long sum = 0L;
for (int i = 0; i < letter.length; i++) {
sum = (sum + dfs(letter[i], 1, n)) % mod;
}
return (int) sum;
}
private long dfs(char pre, int len, int n) {
if (len == n) {
return 1;
}
StringBuilder sb = new StringBuilder();
sb.append(pre).append(len);
if (map.containsKey(sb.toString())) {
return map.get(sb.toString());
}
long res = 0;
for (char c : letter) {
if (pre == 'a' && c == 'e') {
res += dfs(c, len + 1, n);
} else if (pre == 'e' && (c == 'a' || c == 'i')) {
res += dfs(c, len + 1, n);
} else if (pre == 'i' && c != 'i') {
res += dfs(c, len + 1, n);
} else if (pre == 'o' && (c == 'i' || c == 'u')) {
res += dfs(c, len + 1, n);
} else if (pre == 'u' && c == 'a') {
res += dfs(c, len + 1, n);
}
res %= mod;
// 记忆化搜索
map.put(sb.toString(), res);
}
return res;
}复杂度分析：n 是输入的整数
- 时间复杂度：$O(C^2*n)$
- 空间复杂度：$O(C*n)$
本文作者：
Chthollists
发布时间： 2022-01-17 16:03:21
最后更新： 2022-01-21 23:09:05
本文标题： LeetCode:1220.统计元音字母序列的数目：「状态DP」&「矩阵快速幂」
本文链接： https://chthollists.github.io/post/d19fc25f.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！
发布时间： 2022-01-17 16:03:21
最后更新： 2022-01-21 23:09:05
本文标题： LeetCode:1220.统计元音字母序列的数目：「状态DP」&「矩阵快速幂」
本文链接： https://chthollists.github.io/post/d19fc25f.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！
