題目

核心思路

題目的含義還是挺好理解的荔睹，作為周賽的第二題也還算中規(guī)中矩揖盘。我們需要找到長度為n的楷力、按字典序排列的喊式、僅由元音字母組成的字符串?dāng)?shù)量。其中最重要的就是要滿足按字典序排列萧朝，也就是示例二所說的"ea" 不是符合題意的字符串岔留，因?yàn)?'e' 在字母表中的位置比 'a' 靠后。

暴力法(深搜检柬、寬搜)

理解了題意献联，直接使用深搜或者寬搜模擬拼接的過程就可以了，可以先確定第一個(gè)字符為c(c表示一個(gè)元音字符)，那么他后邊能接的只有大于或等于他的字符里逆，接著來處理他后邊的那個(gè)字符进胯，形成了一個(gè)遞歸的過程，就可以很容易得出答案了原押。而遞歸出口胁镐，就是字符串的長度為目標(biāo)值n即可。
注意：因?yàn)閷?shí)際上我們只需要拼接字符串的最后一個(gè)字符诸衔，所以直接對(duì)字符而非字符串遞歸即可希停，這樣可以節(jié)省很多時(shí)間。

暴力法代碼

class Solution {
    
    char[] chars = {'a', 'e', 'i', 'o', 'u'};
    
    public int countVowelStrings(int n) {
        int res = 0;
        
        for(char c : chars){
            res += solve(c, n);
        }
        return res;
    }
    
    public int solve(char c, int n){
        if(n == 1) return 1;
        
        int idx = 5;
        int res = 0;
        for(int i = 0; i < chars.length; i++){
            if(chars[i] == c){
                idx = i;
            }
            if(i >= idx){
                res += solve(chars[i], n - 1);
            }
        }
        return res;
    }
}

這里使用遞歸的方式實(shí)現(xiàn)署隘，迭代方式思想也是一樣的宠能，就不再過多贅述。

動(dòng)態(tài)規(guī)劃法

觀察暴力法磁餐，在函數(shù)參數(shù)c, n相同的情況下违崇，返回的結(jié)果也是肯定相同的，而在函數(shù)調(diào)用中可能會(huì)多次調(diào)用同一個(gè)函數(shù)诊霹，因此不妨直接記錄dp[c][n] 表示以字符c開頭羞延，長度為n的滿足條件的字符串的數(shù)量。當(dāng)然直接當(dāng)做記憶化遞歸完善上邊代碼倒也是可以的脾还，不過由于只有5個(gè)字符伴箩，完全可以迭代一層循環(huán)解決，會(huì)簡便不少鄙漏。
我們考慮下邊的例子：n = 5
如果對(duì)所有結(jié)果分類的話嗤谚，可以分為：

• 以 a 開頭的長度為n字符串?dāng)?shù)量
• 以 e 開頭的長度為n字符串?dāng)?shù)量
• 以 i 開頭的長度為n字符串?dāng)?shù)量
• 以 o 開頭的長度為n字符串?dāng)?shù)量
• 以 u 開頭的長度為n字符串?dāng)?shù)量

那么以 a 開頭的字符串又有什么規(guī)律呢？它的后邊5種字符都可以接怔蚌，也就是按上述遞歸巩步，包含以 'a' 開頭長度為 'n - 1'的字符串?dāng)?shù)量、以 'e'開頭長度為 ‘n - 1' 的字符串的數(shù)量……最終桦踊，也就是長度為一的字符串的數(shù)量椅野，均為1，可以直接初始化籍胯。
因此就可以得到如下的遞推公式：

    dp[4][i] = dp[4][i - 1];
    dp[3][i] = dp[3][i - 1] + dp[4][i];
    dp[2][i] = dp[2][i - 1] + dp[3][i];
    dp[1][i] = dp[1][i - 1] + dp[2][i];
    dp[0][i] = dp[0][i - 1] + dp[1][i];

其中的dp[0]竟闪、dp[1]、dp[2]......分別對(duì)應(yīng)了字符a, e, i, o, u開頭杖狼，因?yàn)榘凑盏剐?code>u, o, i, e, a的方式遍歷炼蛤，避免了中間重復(fù)加的數(shù)值，稍微簡化了點(diǎn)代碼本刽。

動(dòng)態(tài)規(guī)劃代碼

class Solution {
    public int countVowelStrings(int n) {
        int[][] dp = new int[5][n];
        dp[0][0] = dp[1][0] = dp[2][0] = dp[3][0] = dp[4][0] = 1;
        for(int i = 1; i < n; i++){
            dp[4][i] = dp[4][i - 1];
            dp[3][i] = dp[3][i - 1] + dp[4][i];
            dp[2][i] = dp[2][i - 1] + dp[3][i];
            dp[1][i] = dp[1][i - 1] + dp[2][i];
            dp[0][i] = dp[0][i - 1] + dp[1][i];
        }

        return dp[0][n - 1] + dp[1][n - 1] + dp[2][n - 1] + dp[3][n - 1] + dp[4][n - 1];
    }
}

這樣避免了字符串的拼接以及重復(fù)的函數(shù)調(diào)用(記憶化遞歸結(jié)果也是相同的)鲸湃，時(shí)間復(fù)雜度O(N)，效率大大提升子寓。

排列組合法

感謝零神的題解暗挑，使用排列組合的隔板法，直接計(jì)算最終結(jié)果即可斜友。
不過由于隔板法要保證兩個(gè)隔板中間含有元素炸裆，而在本題中是可以不含元素的，所以可以給所有的n個(gè)位置中添加5個(gè)虛位置鲜屏，來保證至少有一個(gè)元素烹看，因?yàn)槭?strong>虛位置，插入板之后要?jiǎng)h掉洛史，這樣就使得兩個(gè)隔板中間可以沒有元素了惯殊。
因此總共就有n + 5個(gè)位置，中間的間隔可以插板的位置就有n + 4個(gè)也殖，由于最終要?jiǎng)澐譃?種元音字母土思，因此需要插的隔板有4個(gè)。也就是在n + 4個(gè)位置中取4個(gè)位置忆嗜，結(jié)果也就是：

排列組合法代碼

class Solution {
    public int countVowelStrings(int n) {
        return (n + 4) * (n + 3) * (n + 2) * (n + 1) / (4 * 3 * 2);
    }
}

這一次周賽的數(shù)學(xué)問題真的很多，雖然其他方法也可以解決捆毫，總歸還是感覺差那么點(diǎn)事兒闪湾，數(shù)學(xué)終歸還是算法的歸處啊。
文章有寫的不對(duì)的地方還請(qǐng)指出绩卤，感恩相遇~