Appearance
题目
给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。
字符串 s 按 字典序排列 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。
示例 1：
输入：n = 1
输出：5
解释：仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]输入：n = 1
输出：5
解释：仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]示例 2：
输入：n = 2
输出：15
解释：仅由元音组成的 15 个字典序字符串为
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
注意，"ea" 不是符合题意的字符串，因为 'e' 在字母表中的位置比 'a' 靠后输入：n = 2
输出：15
解释：仅由元音组成的 15 个字典序字符串为
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
注意，"ea" 不是符合题意的字符串，因为 'e' 在字母表中的位置比 'a' 靠后示例 3：
输入：n = 33
输出：66045输入：n = 33
输出：66045提示：
- 1 <= n <= 50
理解题目
给定一个长度 n，按元音字母的顺序进行组成排列的字符串，这个字符串的长度不能超过 n，而且不可以将顺序调换进行组成例如'ea'，最后返回组成的一种有多少种
题解
拿示例 2 来看，a 只能作为 a 自己的结尾，e 可以作为 a 和 e 的结尾，以此类推 u 可以作为所有元音的结尾了。
假设利用一个数组 dp[i]存取我们的每个元音结尾的个数，起始都是 1，那么 a 的个数就是 dp[0],e 的个数就是 dp[0]+dp[1] u 的个数就是 dp[0]+dp[1]+dp[2]+dp[3]+dp[4]
dp[0]=1
dp[1]=dp[1]+dp[0]
dp[2]=dp[2]+dp[1]+dp[0]
dp[3]=dp[3]+dp[2]+dp[1]+dp[0]
dp[4]=dp[4]+dp[3]+dp[2]+dp[1]+dp[0]dp[0]=1
dp[1]=dp[1]+dp[0]
dp[2]=dp[2]+dp[1]+dp[0]
dp[3]=dp[3]+dp[2]+dp[1]+dp[0]
dp[4]=dp[4]+dp[3]+dp[2]+dp[1]+dp[0]而组成的数量是当 1 到 n 时的 dp 内数组次数的相加，因为我们的下标是从 0 开始的，如果我们是 n=2 的话，这样我们就会遍历了 3 次，就会出现长度为 3 的字符串，但是需要的是长度为 2 的字符串，所以我们需要从下标为 1 开始。
所以状态转移方程是dp[i] = dp[i]+dp[i-1]+...+dp[0]
答案
ts
function countVowelStrings(n: number): number {
let dp = new Array(5).fill(1);
for (let i = 1; i < n; i++) {
for (let j = 4; j >= 0; j--) {
// 字母j（从u开始）
for (let k = j - 1; k >= 0; k--) {
// 字母 j 前面的字母都可以用 j 当作结尾
dp[j] = dp[j] + dp[k];
}
}
}
let num = dp.reduce((a, b) => a + b);
return num;
}function countVowelStrings(n: number): number {
let dp = new Array(5).fill(1);
for (let i = 1; i < n; i++) {
for (let j = 4; j >= 0; j--) {
// 字母j（从u开始）
for (let k = j - 1; k >= 0; k--) {
// 字母 j 前面的字母都可以用 j 当作结尾
dp[j] = dp[j] + dp[k];
}
}
}
let num = dp.reduce((a, b) => a + b);
return num;
}