题目描述

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

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

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

样例

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

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

输入：n = 5
输出：68

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

算法

(DP) $O(n)$

• f[0]代表a f[1]代表e f[2]代表i f[3]代表o f[4]代表u

• f[i]代表以对应字母结尾满足规则的长度

• pre代表上一个长度状态的对应字母结尾满足规则的长度
  f[0] = pre[2] + pre[1] + pre[4];
  f[1] = pre[2] + pre[0];
  f[2] = pre[1] + pre[3];
  f[3] = pre[2];
  f[4] = pre[2] + pre[3];

解释：

根据题意反过来推, a的前面只能跟着i e u, e的前面只能跟着i a, i的前面只能跟着e u, o的前面只能跟着i, u的前面只能跟着i o

所以f[i]当前长度为k的时候, 可以在k-1长度的字母后面添加上对应的字母（即pre[i]) 求出f[i]。每次只有上一个状态决定，所以可以使用滚动数组。

最后在统计以每个字母结尾长度为n的数目即为答案。

C++ 代码

const int MOD = 1e9+7;

class Solution {
// a e i o u
// 0 1 2 3 4

private:
    long long f[5] = {1, 1, 1, 1, 1};  // f[i]代表以对应字母结尾满足规则的长度

public:
    int countVowelPermutation(int n) {
        long long pre[5] = {1, 1, 1, 1, 1};  // 因为使用滚动数组，保存f[i-1]的状态用于获取
        for (int i = 2; i <= n; i++) {
            f[0] = pre[2] + pre[1] + pre[4];  // a
            f[1] = pre[2] + pre[0];           // e
            f[2] = pre[1] + pre[3];           // i
            f[3] = pre[2];                    // o
            f[4] = pre[2] + pre[3];           // u
            for (int i = 0; i < 5; i++) pre[i] = f[i] % MOD;
        }

        long long res = 0;
        for (const auto& x : f) {
            res += x;
            res %= MOD;
        }
        return res;
    }
};