給你一個整數(shù) n，請你幫忙統(tǒng)計一下我們可以按下述規(guī)則形成多少個長度為n的字符串：

字符串中的每個字符都應(yīng)當(dāng)是小寫元音字母（'a', 'e', 'i', 'o', 'u'）
每個元音 'a' 后面都只能跟著 'e'
每個元音 'e' 后面只能跟著'a'或者是'i'
每個元音 'i'后面 不能 再跟著另一個'i'
每個元音'o'后面只能跟著'i' 或者是'u'
每個元音'u'后面只能跟著 'a'
由于答案可能會很大，所以請你返回 模 10^9 + 7之后的結(jié)果。

示例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

這道題的想法就是計算當(dāng)有1到n個字符時，字符串可能的組成種數(shù)。由于字符串只能由a、e、i、 o、 u組成，令k表示當(dāng)前計算的字符串的長度，a[k][0]表示字符串長度為k時，第k個字符為a的字符串組成種數(shù)。以此類推，a[k][1]表示第k個字符為e的字符串組成種數(shù)，a[k][2]為i的組成種數(shù)，a[k][3]為o的組成種數(shù)，a[k][4]為u的組成種數(shù)。

由給定的規(guī)則知，如果第k個字符要為a時，則第k-1個字符只能為e、i、u ，因此第k個字符為a的字符串組成種數(shù)即為第k-1個字符為e、i、u時的字符串組成種數(shù)，即a[k][0] = a[k-1][1]+a[k-1][2]+a[k-1][4]。當(dāng)?shù)趉個字符為e、i、 o、 u的情況可以依次類推。

一開始我沒有取模，報數(shù)字溢出錯誤。google了一下，看到這篇文章說在進行加法時取模不會影響最后地結(jié)果，就大膽地取模了。

class Solution {
public:
    int countVowelPermutation(int n) {
        int M = pow(10,9)+7;
        vector<vector<long long int>> a(n);
        for(int i=0;i<n;i++){
            a[i].resize(5);
        }
        for(int i=0;i<5;i++){
            a[0][i] = 1;
        }
        for(int i=0;i<n-1;i++){
            a[i+1][0] = (a[i][1]+a[i][2]+a[i][4]) % M;
            a[i+1][1] = (a[i][0]+a[i][2]) % M;
            a[i+1][2] = (a[i][1]+a[i][3]) % M;
            a[i+1][3] = (a[i][2]) % M;
            a[i+1][4] = (a[i][2]+a[i][3])%M;
        }
        return (a[n-1][0]+a[n-1][1]+a[n-1][2]+a[n-1][3]+a[n-1][4])%M;
    }
};

題目鏈接：https://leetcode.com/contest/weekly-contest-157/problems/count-vowels-permutation/