# 【LeetCode】 1641. Count Sorted Vowel Strings

## Description
> Given an integer `n`, return the number of strings of length `n` that consist only of vowels (`a`, `e`, `i`, `o`, `u`) and are lexicographically sorted.
>
> A string `s` is lexicographically sorted if for all valid `i, s[i]` is the same as or comes before `s[i+1]` in the alphabet.

> 給予一正整數 `n`，回傳所有只包含母音 (`a`, `e`, `i`, `o`, `u`)、按照字典順序排序的字串數量。
>
> 一個字串 `s` 如果是按字典順序排序，表示對於所有有效的 `i, s[i]` 來說，`s[i+1]` 一定和他相同或是在它之前。

* 限制：
`1 <= n <= 50 `

## Example:

Example 1:

Input: n = 1
Output: 5
Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].

Example 2:

Input: n = 2
Output: 15
Explanation: The 15 sorted strings that consist of vowels only are
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"].
Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.

Example 3:

Input: n = 33
Output: 66045

## Solution

* 先利用枚舉來觀察規律
* n = 1 的時候只有 aeiou
* n = 2 時
* a 有 5
* e 有 4
* i 有 3
* o 有 2
* u 有 1
* n = 3 時
* a 有 15 (15 - 0)
* e 有 10 (15 - 5)
* i 有 6 (15 - 5 - 4)
* o 有 3 (15 - 5 - 4 - 3)
* u 有 1 (15 - 5 - 4 - 3 - 2)
* 可以發現規律是上一次的總和(sum of 0~5) - 上一次到自己為止的總和(sum of 0~i)

### Code

class Solution {
public:
    int sumTable(int* table, int size)
    {
        int sum = 0;
        
        for(int i = 0; i < size; i++)
            sum += table[i];
        
        return sum;
    }
    int countVowelStrings(int n) {
        if(n == 1)
            return 5;
        /*
        5 aa ae ai ao au
        4    ee ei eo eu
        3       ii io iu
        2          oo ou
        1             uu
        */
        int table[] = {5, 4, 3, 2, 1};
        int preTable[] = {0, 5, 9, 12, 14};
        
        for(int i = 2; i < n; i++)
        {
            int sum = sumTable(table, 5);
            for(int j = 0; j < 5; j++)
            {
                table[j] = sum - preTable[j];
                preTable[j] = sumTable(table, j);
            }
        }
        
        return sumTable(table, 5);
    }
};

###### tags: `LeetCode` `C++`