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

标签：动态规划
难度：困难

题目大意 #

描述：给定一个整数 n，我们可以按照以下规则生成长度为 n 的字符串：

字符串中的每个字符都应当是小写元音字母（'a'、'e'、'i'、'o'、'u'）。
每个元音 'a' 后面都只能跟着 'e'。
每个元音 'e' 后面只能跟着 'a' 或者是 'i'。
每个元音 'i' 后面不能再跟着另一个 'i'。
每个元音 'o' 后面只能跟着 'i' 或者是 'u'。
每个元音 'u' 后面只能跟着 'a'。

要求：统计一下我们可以按上述规则形成多少个长度为 n 的字符串。由于答案可能会很大，所以请返回模 $10^9 + 7$ 之后的结果。

说明：

$1 \le n \le 2 * 10^4$。

示例：

示例 1：

1
2
3


输入：n = 2
输出：10
解释：所有可能的字符串分别是："ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" 和 "ua"。

解题思路 #

思路 1：动态规划 #

根据题目给定的字符串规则，我们可以将其整理一下：

元音字母 'a' 前面只能跟着 'e'、'i'、'u'。
元音字母 'e' 前面只能跟着 'a'、'i'。
元音字母 'i' 前面只能跟着 'e'、'o'。
元音字母 'o' 前面只能跟着 'i'。
元音字母 'u' 前面只能跟着 'o'、'i'。

现在我们可以按照字符串的长度以及字符结尾进行阶段划分，并按照上述规则推导状态转移方程。

1. 划分阶段 #

按照字符串的结尾位置和结尾位置上的字符进行阶段划分。

2. 定义状态 #

定义状态 dp[i][j] 表示为：长度为 i 并且以字符 j 结尾的字符串数量。这里 $j = 0, 1, 2, 3, 4$ 分别代表元音字母 'a'、'e'、'i'、'o'、'u'。

3. 状态转移方程 #

通过上面的字符规则，可以得到状态转移方程为：

$\begin{cases} dp[i][0] = dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][4] \cr dp[i][1] = dp[i - 1][0] + dp[i - 1][2] \cr dp[i][2] = dp[i - 1][1] + dp[i - 1][3] \cr dp[i][3] = dp[i - 1][2] \cr dp[i][4] = dp[i - 1][2] + dp[i - 1][3] \end{cases}$

4. 初始条件 #

长度为 1 并且以字符 j 结尾的字符串数量为 1，即 dp[1][j] = 1。

5. 最终结果 #

根据我们之前定义的状态，dp[i] 表示为：长度为 i 并且以字符 j 结尾的字符串数量。则将 dp[n] 行所有列相加，就是长度为 n 的字符串数量。

思路 1：动态规划代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        mod = 10 ** 9 + 7
        dp = [[0 for _ in range(5)] for _ in range(n + 1)]

        for j in range(5):
            dp[1][j] = 1

        for i in range(2, n + 1):
            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

        ans = 0
        for j in range(5):
            ans += dp[n][j] % mod
        ans %= mod
        
        return ans

思路 1：复杂度分析 #

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