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

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
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)$。
本站总访问量  次  |  您是本站第  位访问者