# Leetcode 解題速記 1220. Count Vowels Permutation
###### tags: `LeetCode` `C++`
題敘:
---
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.

Example 1:

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

Example 2:

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

Example 3:

Input: n = 5
Output: 68

測資範圍:
---
* `1 <= n <= 2 * 10^4`

解題筆記:
---
閱讀完題目後，第一時間想到是用DP解題

根據題目敘述可以發現，當n = 1時，每一種字元都只有一種組合，而n = 2時，合法的字元組合則取決於第二個字元與第一個字元的連結是否符合規則。
以此類推，當我們求長度為n的所有可能字串時，我們要考慮所有n-1長度的可能字串與他們的第n-1個字元，並依照第n個字元與第n-1個字元的連結規則來得出所有合法字串。

以n = 3為例，假設我們第三個字元為`i`，根據規則可以得出所有尾部字元為`e,o`的長度2字串可以與`i`連結，也就是`'ae','ie','io'`這三種組合。根據這個規則，可以得到其他字元`a,e,o,u`分別有6、5、2、3種組合。因此n = 3的字串有3+6+5+2+3共19種組合。

這邊使用每個字元各一個long int來記憶第一到第n個字串的組合數量，並設定基底為1。轉移式的部分則跟每個字元的規則有關，以a為例就是 :
`a(n) = e(n-1) + i(n-1) + u(n-1)`
這邊`a(n)`的意思就是第n個字元為a的所有可能組合，因此`sum(a,e,i,o,u)`就是我們要的答案。

程式碼:
---
`Time Complexity : O(n)`

class Solution {
public:
    int countVowelPermutation(int n) {
        constexpr int mod = 1e9 + 7;
        long a = 1, e = 1, i = 1, o = 1, u = 1;

        for (int j = 2; j <= n; j++)
        {
            long a_ = (e + i + u) % mod;
            long e_ = (a + i) % mod;
            long i_ = (e + o) % mod;
            long o_ = i % mod;
            long u_ = (i + o) % mod;
            a = a_;
            e = e_;
            i = i_;
            o = o_;
            u = u_;
        }

        return (a + e + i + o + u) % mod;
    }
};