# [LeetCode 1220. Count Vowels Permutation](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/608/week-1-july-1st-july-7th/3802/)
### Daily challenge Jul 4, 2021 (HARD)

>Given an integer n, your task is to count how many strings of length n can be formed under the following rules:
>
>* Each character is a lower case vowel ('a', 'e', 'i', 'o', 'u')
>* Each vowel 'a' may only be followed by an 'e'.
>* Each vowel 'e' may only be followed by an 'a' or an 'i'.
>* Each vowel 'i' **may not** be followed by another 'i'.
>* Each vowel 'o' may only be followed by an 'i' or a 'u'.
>* Each vowel 'u' may only be followed by an 'a'.
>
>Since the answer may be too large, return it **modulo** 10^9^ + 7.

:::info
**Example 1:**
**Input:** n = 1
**Output:** 5
**Explanation:** All possible strings are: "a", "e", "i" , "o" and "u".
:::

:::info
**Example 2:**
**Input:** n = 2
**Output:** 10
**Explanation:** All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".
:::

:::info
**Example 3:**
**Input:** n = 5
**Output:** 68
:::

:::warning
**Constraints:**
* 1 <= n <= 2 * 10^4^
:::

---

### Approach 1 : DP :book:
**`4 ms ( 84.02% ) by long[]`** **`O(N)`**
**`60 ms ( 28.75% ) by vecotr`**

:::success
**`dp[n][#]`** 代表長度 **n** 且結尾為 **#** 的所有可能。
因此可以知道 **`dp[n+1][x] = sum of all dp[n][y]`** ( y 可連接到 x )。
:::

> 先將五個母音進行編號 **`A(0), E(1), I(2), O(3), U(4)`**.
> 根據下圖，可以發現以下規則 :
>> **`1. dp[i][A] = dp[i-1][E] + dp[i-1][I] + dp[i-1][U]`**.
> **`2. dp[i][E] = dp[i-1][A] + dp[i-1][I]`**.
> **`3. dp[i][I] = dp[i-1][E] + dp[i-1][O]`**.
> **`4. dp[i][O] = dp[i-1][I]`**.
> **`5. dp[i][U] = dp[i-1][I] + dp[i-1][O]`**.
>
> 最後 **`sum of dp[n][#]`** 即為答案。


class Solution {
public:
    int countVowelPermutation(int n) {
        // 0 1 2 3 4 //
        // a e i o u //
        
        #define MOD 1000000007
        
        //vector<vector<long> > dp(n+1, vector<long>(5, 0));
        long dp[n+1][5];
        
        for(int i=0; i<5; i++){
            dp[1][i] = 1;
        }
        
        for(int i=2; i<=n; i++){
            dp[i][0] = (dp[i-1][1] + dp[i-1][2] + dp[i-1][4]) % MOD;    // a = e + i + u
            dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % MOD;                 // e = a + i
            dp[i][2] = (dp[i-1][1] + dp[i-1][3]) % MOD;                 // i = e + o
            dp[i][3] = (dp[i-1][2]) % MOD;                              // o = i
            dp[i][4] = (dp[i-1][2] + dp[i-1][3]) % MOD;                 // u = i + o
        }

        return (dp[n][0] + dp[n][1] + dp[n][2] + dp[n][3] + dp[n][4]) % MOD;
    }
};