原贴地址：https://dawnmagnet.github.io/algorithm-station/docs/2022/1/17

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-vowels-permutation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路分析

#

本道题其实就是一个找规律分析题，科学一点的讲法叫做动态规划，但真的挺简单的。

根据题目中的意思，我们可以看出，题目所谓的“元音字母序列”实际上就是只跟最后一位字母有关系，也就是说，对于一个序列，我们压根没必要知道它前面是啥，只要告诉我们最后一位字母是啥，就可以继续往下进行扩展了。在这种条件下，我们可以只使用一个数组，保存序列末尾分别对应aeiou时的序列数量，就能大大简化计算。

然后根据题目中的条件，自行推导一下，可以发现

• a前面可以是eiu
• e前面可以是ai
• i前面可以是eo
• o前面可以是i
• u前面可以是io

根据这个条件，就可以实现递推式

在计算出来指定的那一步aeiou结尾的序列分别有多少个之后，再对其进行一个简单的相加就可以获得答案。

Rust代码

#

const m: i64 = 1_000_000_007;
impl Solution {
    pub fn count_vowel_permutation(n: i32) -> i32 {
        let mut c = [1i64, 1, 1, 1, 1];
        for i in 1..n {
            c = [
                (c[1] + c[2] + c[4]) % m,
                (c[0] + c[2]) % m,
                (c[1] + c[3]) % m,
                c[2],
                (c[2] + c[3]) % m,
            ];
        }
        (c.iter().sum::<i64>() % m) as i32
    }
}