题目描述

给定一个整数 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

限制

• 1 <= n <= 50

算法

(动态规划) $O(n)$

1. 设状态 $f(i, j)$ 表示构造前 $i$ 个字符，以元音 $j$ 结尾的方案数。$i$ 的有效下标从 0 开始，$j$ 的范围是 0 到 4。
2. 初始时，$f(0, j) = 1$，其余为 0。
3. 转移时，对于 $f(i, j)$，设 $0 \le k \le j$，则其可以从 $f(i - 1, k)$ 转移，即 $f(i, j) = f(i, j) + f(i - 1, k)$。
4. 最终答案为 $\sum_{j=0}^{4}{f(n - 1, j)}$。

时间复杂度

• 状态数为 $O(n)$，转移时间为常数，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储状态。

C++ 代码

class Solution {
public:
    int countVowelStrings(int n) {
        vector<vector<int>> f(n, vector<int>(5, 0));
        for (int j = 0; j < 5; j++)
            f[0][j] = 1;

        for (int i = 1; i < n; i++)
            for (int j = 0; j < 5; j++)
                for (int k = 0; k <= j; k++)
                    f[i][j] += f[i - 1][k];

        int ans = 0;
        for (int j = 0; j < 5; j++)
            ans += f[n - 1][j];
        return ans;
    }
};