题目

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

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

• 每个元音 'a' 后面都只能跟着 'e'
• 每个元音 'e' 后面只能跟着 'a' 或者是 'i'
• 每个元音 'i' 后面不能再跟着另一个 'i'
• 每个元音 'o' 后面只能跟着 'i' 或者是 'u'
• 每个元音 'u' 后面只能跟着 'a'

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

来源：力扣（LeetCode）

解答

题目对五个元音字母 a, e, i, o, u 有一定的排列规则，当n = 1时，肯定是这五个元音字母。

当n增大时，所构成的序列数目与n-1相关，且与n-1的最后一个字母有关，所以可以建立一个大小为5的整数数组，分别表示给定n值时，分别以a, e, i, o, u结尾的序列数目，且状态转移规律为：

• num[n][a] = num[n-1][e] + num[n-1][i] + num[n-1][u]
• num[n][e] = num[n-1][a] + num[n-1][i]
• num[n][i] = num[n-1][e] + num[n-1][o]
• num[n][o] = num[n-1][i]
• num[n][u] = num[n-1][i] + num[n-1][o]

依次按照状态转移进行动态规划，并进行取模即可。

代码如下：

class Solution {
public:
    const long long int mod = 1000000007;

    // a e i o u
    int countVowelPermutation(int n) {
        long long int cur[5] = {1, 1, 1, 1, 1};
        long long int last[5] = {0};

        while (--n) {
            for (int i = 0; i < 5; ++i) {
                last[i] = cur[i];
            }

            cur[0] = (last[1] + last[2] + last[4]) % mod; // 先进行一次mod，避免值过大
            cur[1] = (last[0] + last[2]) % mod;
            cur[2] = (last[1] + last[3]) % mod;
            cur[3] = last[2] % mod;
            cur[4] = (last[2] + last[3]) % mod;
        }

        return (cur[0] + cur[1] + cur[2] + cur[3] + cur[4]) % mod;
    }
};