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

难度：困难

(https://leetcode.cn/problems/count-vowels-permutation/)

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

1. 字符串中的每个字符都应当是小写元音字母（‘a’, ‘e’, ‘i’, ‘o’, ‘u’）

2. 每个元音 ‘a’ 后面都只能跟着 ‘e’

3. 每个元音 ‘e’ 后面只能跟着 ‘a’ 或者是 ‘i’

4. 每个元音 ‘i’ 后面 不能 再跟着另一个 ‘i’

5. 每个元音 ‘o’ 后面只能跟着 ‘i’ 或者是 ‘u’

6. 每个元音 ‘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字母结尾的长度为n的序列，只能来自于以e，u，i结尾的长度为n-1的序列，其他以此类推。

class Solution {
    public int countVowelPermutation(int n) {
        long a=1,e=1,i=1,o=1,u=1;
        long  m = 1000000000 + 7;
        for(int x = 2; x <= n; x++){
            long aa = (e + u + i) % m;
            long ee = (a + i) % m;
            long ii = (e + o) % m;
            long oo =  i % m;
            long uu = (i + o) % m;
            a = aa;
            e = ee;
            i = ii;
            o = oo;
            u = uu;
        }
        return (int)((a+e+i+o+u)%m);
    }
}