題目

核心思路

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

暴力法(深搜、寬搜)

理解了題意，直接使用深搜或者寬搜模擬拼接的過程就可以了，可以先確定第一個(gè)字符為c(c表示一個(gè)元音字符)，那么他后邊能接的只有大于或等于他的字符，接著來處理他后邊的那個(gè)字符，形成了一個(gè)遞歸的過程，就可以很容易得出答案了。而遞歸出口，就是字符串的長(zhǎng)度為目標(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開頭，長(zhǎng)度為n的滿足條件的字符串的數(shù)量。當(dāng)然直接當(dāng)做記憶化遞歸完善上邊代碼倒也是可以的，不過由于只有5個(gè)字符，完全可以迭代一層循環(huán)解決，會(huì)簡(jiǎn)便不少。
我們考慮下邊的例子：n = 5
如果對(duì)所有結(jié)果分類的話，可以分為：

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

那么以 a 開頭的字符串又有什么規(guī)律呢？它的后邊5種字符都可以接，也就是按上述遞歸，包含以 'a' 開頭長(zhǎng)度為 'n - 1'的字符串?dāng)?shù)量、以 'e'開頭長(zhǎng)度為 ‘n - 1' 的字符串的數(shù)量……最終，也就是長(zhǎng)度為一的字符串的數(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ù)值，稍微簡(jiǎn)化了點(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)指出，感恩相遇~