2021-09-21-count-vowel-strings.md

title	date	permalink	tags
count sorted vowel strings	2021-09-21	/posts/2021/09/count-vowel-strings/	dynamic programming

统计字典じてん序じょ元もと音字おんじ符ふ串くし的てき数すう目もく

题目描述

给你一いち个整数すうn, 请返回かい长度为 n ，仅由元もと音おとa,e,i,o,u 组成且按字典じてん序じょ排列はいれつ的てき字じ符ふ串くし数量すうりょう。

字じ符ふ串くし s 按 字典じてん序じょ排列はいれつ 需要じゅよう满足：对于所有しょゆう有效ゆうこう的てき i，s[i] 在ざい字母じぼ表ひょう中ちゅう的てき位置いち总是与あずか s[i+1] 相あい同どう或ある在ざい s[i+1] 之の前まえ。

输入：n = 1
输出：5
解かい释：仅由元もと音おと组成的てき 5 个字典じてん序じょ字じ符ふ串くし为 ["a","e","i","o","u"]

输入：n = 2
输出：15
解かい释：仅由元もと音おと组成的てき 15 个字典じてん序じょ字じ符ふ串くし为
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
注意ちゅうい，"ea" 不ふ是ぜ符合ふごう题意的てき字じ符ふ串くし，因いん为 'e' 在ざい字母じぼ表ひょう中ちゅう的てき位置いち比ひ 'a' 靠もたれ后きさき

输入：n = 33
输出：66045

解法かいほう一いち： 无脑数学すうがく

等とう价于把わn个字母はは分ぶん给五种元音おん，且分配ぶんぱい数すう目もく可か以为零れい，就是求もとめc(n+4, n) = c(n+4, 4)

class Solution {
public:
    int countVowelStrings(int n) {
        if (n == 1) return 5;
        return (n + 4) * (n + 3) * (n + 2) * (n + 1) / 24;
    }
};

解法かいほう二に： 动态规划

a可か以加在ざい（aeiou）之の前まえ，e可か以加在ざい(eiou)之の前まえ，以此类推

就是求もとめn-1次じ前まえ缀和

class Solution {
public:
    int countVowelStrings(int n) {
        vector<int> cnt(5, 1);
        while(--n) partial_sum(begin(cnt), end(cnt), begin(cnt));
        return accumulate(begin(cnt), end(cnt), 0);
    }
};