1641. 统计字典序元音字符串的数目 给你一个整数 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’ 靠后

提示：

• 1 <= n <= 50

Solutions

class Solution {
    public int countVowelStrings(int n) {
        if(n==0) return 0;
        int[] dp = {1,1,1,1,1};
        for(int i=2;i<=n;i++){
            for(int j = 0;j<5;j++){
                for(int k =j+1;k<5;k++){
                    dp[j]+=dp[k];
                }
            }
        }
        return dp[0]+dp[1]+dp[2]+dp[3]+dp[4];
    }
}

Ideas

方法一：动态规划 分别使用数字 0，1，2，3，4 代表元音字符 ‘a’，‘e’，‘i’，‘o’，‘u’。记 dp[i][j] 表示长度为 i+1，以 j 结尾的按字典序排列的字符串数量，那么状态转移方程如下：

dp[i][j]=1 i=0 dp[i][j]=∑ j k=0 dp[i−1][k] i>0

因此长度为 n 的按字典序排列的字符串数量为 ∑ 4 k=0 dp[n−1][j]。因为 dp[i] 的计算只涉及 dp[i−1] 部分的数据，同时 dp[i] 等价于 dp[i−1] 的前缀和，我们可以只使用一维数组进行存储，同时在一维数组进行原地修改。