題目

核心思路

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

暴力法(深搜、寬搜)

理解了題意，直接使用深搜或者寬搜模擬拼接的過程就可以了，可以先確定第一個字符為c(c表示一個元音字符)，那么他后邊能接的只有大于或等于他的字符，接著來處理他后邊的那個字符，形成了一個遞歸的過程，就可以很容易得出答案了。而遞歸出口，就是字符串的長度為目標值n即可。
注意：因為實際上我們只需要拼接字符串的最后一個字符，所以直接對字符而非字符串遞歸即可，這樣可以節(jié)省很多時間。

暴力法代碼

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;
    }
}

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

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

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

• 以 a 開頭的長度為n字符串數(shù)量
• 以 e 開頭的長度為n字符串數(shù)量
• 以 i 開頭的長度為n字符串數(shù)量
• 以 o 開頭的長度為n字符串數(shù)量
• 以 u 開頭的長度為n字符串數(shù)量

那么以 a 開頭的字符串又有什么規(guī)律呢？它的后邊5種字符都可以接，也就是按上述遞歸，包含以 'a' 開頭長度為 'n - 1'的字符串數(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]......分別對應了字符a, e, i, o, u開頭，因為按照倒序u, o, i, e, a的方式遍歷，避免了中間重復加的數(shù)值，稍微簡化了點代碼。

動態(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];
    }
}

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

排列組合法

感謝零神的題解，使用排列組合的隔板法，直接計算最終結(jié)果即可。
不過由于隔板法要保證兩個隔板中間含有元素，而在本題中是可以不含元素的，所以可以給所有的n個位置中添加5個虛位置，來保證至少有一個元素，因為是虛位置，插入板之后要刪掉，這樣就使得兩個隔板中間可以沒有元素了。
因此總共就有n + 5個位置，中間的間隔可以插板的位置就有n + 4個，由于最終要劃分為5種元音字母，因此需要插的隔板有4個。也就是在n + 4個位置中取4個位置，結(jié)果也就是：

排列組合法代碼

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

這一次周賽的數(shù)學問題真的很多，雖然其他方法也可以解決，總歸還是感覺差那么點事兒，數(shù)學終歸還是算法的歸處啊。
文章有寫的不對的地方還請指出，感恩相遇~