2022秋招备战！每天写至少一篇Leetcode里Hard难度题目的题解

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

给你一个整数 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

方法一: 动态规划

经过简单的题意分析。我们不难发现，

字母a可以从e, i, u转移而来。

字母e可以从a, i转移而来

字母i可以从e, o转移而来

字母o可以从i转移而来

字母u可以从i, o转移而来。

设$dp[i][j]$代表结尾为$j$，长度为i的数量。

初始化$dp[1][k]$都为1，代表a, e, i, o, u单个字母全部合法。

之后就是很简单的转移。

typedef long long i64;
class Solution {
public:
    const int M = 1e9 + 7;
    int countVowelPermutation(int n) {
        vector<vector<int>> dp (n + 1, vector<int>(5, 0));
        for (int i = 0; i < 5; i++) dp[1][i] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i][0] = ((i64)dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][4]) % M;
            dp[i][1] = ((i64)dp[i - 1][0] + dp[i - 1][2]) % M;
            dp[i][2] = ((i64)dp[i - 1][1] + dp[i - 1][3]) % M;
            dp[i][3] = ((i64)dp[i - 1][2]) % M;
            dp[i][4] = ((i64)dp[i - 1][2] + dp[i - 1][3]) % M;
        }
        int res = 0;
        for (int i = 0; i < 5; i++) {
            res = ((i64)res + dp[n][i]) % M;
        }
        return res % M;
    }
};

可以优化至常数时间复杂度。

typedef long long i64;
class Solution {
public:
    const int M = 1e9 + 7;
    int countVowelPermutation(int n) {
        i64 a = 1, e = 1, i = 1, o = 1, u= 1;
        for (int k = 2; k <= n; k++) {
            i64 A = (e + i + u) % M;
            i64 E = (a + i) % M;
            i64 I = (e + o) % M;
            i64 O = i;
            i64 U = (i + o) % M;
            a = A, e = E, i = I, o = O, u = U;
        }
        i64 res = 0;
        res = a + e + i + o + u;
        return res % M;
    }
};