LeetCode 1220. 统计元音字母序列的数目（DP）

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

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

class Solution {
public:
    int countVowelPermutation(int n) {
    	int mod = 1e9+7;
    	vector<vector<long long>> dp(n+1, vector<long long>(5, 0));
    	dp[1][0] = dp[1][1] = dp[1][2] = dp[1][3] = dp[1][4] = 1;
    	// a 0   e 1   i  2   o 3   u 4
    	//e,i,u --> a   上一个尾部字母 --》 下一个字母
    	//a, i --> e
    	//e o --> i
    	//i -- > o
    	//i o --> u
    	for(int k = 2; k <= n; ++k) 
    	{
    		dp[k][0] = (dp[k-1][1]+dp[k-1][2]+dp[k-1][4])%mod;
    		dp[k][1] = (dp[k-1][0]+dp[k-1][2])%mod;
    		dp[k][2] = (dp[k-1][1]+dp[k-1][3])%mod;
    		dp[k][3] = (dp[k-1][2])%mod;
    		dp[k][4] = (dp[k-1][2]+dp[k-1][3])%mod;
    	}
    	int ans = 0;
    	for(int i = 0; i < 5; i++)
    		ans = (ans+dp[n][i])%mod;
    	return ans;
    }
};