leetcode 周赛 157 5216. 统计元音字母序列的数目 1220. Count Vowels Permutation

目录

1. 题解

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

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

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

示例 1：

输入：n = 1
输出：5
解释：所有可能的字符串分别是："a", "e", "i" , "o" 和 "u"。

示例 2：

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

示例 3：

输入：n = 5
输出：68

提示：

• 1 <= n <= 2 * 10^4

---

题解

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        x = [[1], [0, 2], [0, 3, 1, 4], [2, 4], [0]]
        mod = 10 ** 9 + 7
        dp = [[0 for i in range(5)] for i in range(n)]
        for i in range(5): dp[0][i] = 1
        for i in range(1, n):
            for j in range(5):
                for nt in x[j]:
                    dp[i][j] = (dp[i][j] + dp[i-1][nt]) % mod
        ans = 0 
        for i in range(5):
            ans = (ans + dp[n-1][i]) % mod
        return ans

动态规划，0，1，2，3，4 分别代表 'a', 'e', 'i', 'o', 'u'

dp[n][0] 代表长度为 n 且以 a 开头的的字符串有多少种。dp[n][1]，dp[n][2]，dp[n][3]，dp[n][4]，依次代表长度为 n 且以'a', 'e', 'i', 'o', 'u'开头的字符串的数量。

状态转移方程是：

dp[i][j] = (dp[i][j] + dp[i-1][nt])

当然需要模一个 1e9 + 7。