难度: Medium
给你一个整数 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"]
示例 2：
输入：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
提示：
1 <= n <= 50 运行时间: 21 ms
内存: 16.1 MB
class Solution:
def countVowelStrings(self, n: int) -> int:
if n == 1:
return 5
pre = [1]*5
dp = [1]*5
sum_ = 5
for i in range(1,n):
cnt = sum_
sum_ = 0
for j in range(5):
sum_ += cnt
dp[j] = cnt
cnt -= pre[j]
pre = dp.copy()
#print(dp,sum_)
return sum_
这个题解利用了动态规划的方法来解决问题。首先，初始化一个数组 `pre` 表示长度为 1 的所有情况，每种元音字符各有一个。随后，定义一个 dp 数组来存储当前长度的字符串情况的组合数。变量 `sum_` 用来累加所有的组合数。对于每一个长度从 2 到 n，更新 dp 数组中的每个元素，其中 dp[j] 表示以第 j 个元音结尾的字符串的数量。这是通过累加从当前元音到最后一个元音的组合数来实现的，因为字符串必须按字典序排列。最终，累加所有长度为 n 的组合数得到答案。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def countVowelStrings(self, n: int) -> int:
if n == 1: # 如果长度为1，直接返回5
return 5
pre = [1]*5 # 初始化长度为1的情况
dp = [1]*5 # 初始化dp数组
sum_ = 5 # 初始化sum_为5，因为有5个元音
for i in range(1,n): # 对于每一个长度从2到n
cnt = sum_ # 更新当前所有字符串的组合数
sum_ = 0 # 重置sum_为0
for j in range(5): # 更新dp数组
sum_ += cnt # 累加当前的cnt到sum_
dp[j] = cnt # 更新dp[j]为当前的cnt
cnt -= pre[j] # 减去前一个元音的组合数
pre = dp.copy() # 将当前的dp复制到pre
return sum_ # 返回所有长度为n的组合数
`pre`数组用于存储前一次迭代中，以每个元音字母结尾的字符串的数量。`dp`数组在当前迭代中用同样的方式更新，表示当前长度的字符串数量。通过这种方式，`dp`数组在每一轮循环中根据`pre`数组的值进行更新，确保正确计算出以每个元音结尾的字符串数量，从而利用这些值计算出长度为n的所有字典序元音字符串的总数。
`sum_`在每次迭代开始时存储了所有以任意元音结尾的字符串的总数。将`cnt`更新为`sum_`是为了在当前循环中为每个`dp[j]`计算新的字符串数。`sum_`因此反映了在当前长度下所有可能的字符串组合数，这是因为每次增加字符串长度时，新的字符串都可以在之前的所有字符串后追加任意元音。
在更新`dp`数组时，确保了字符串是按字典序排列的，因为对于每个元音`j`，`dp[j]`的更新是基于从`j`到最后一个元音的所有组合数。这意味着我们只计算那些以该元音或之后的元音结尾的字符串，保持了字典序的正确性。
在每轮迭代中，`dp`数组是基于`pre`数组计算而来的。如果不将`dp`复制到`pre`，则在下一次迭代中，`pre`数组的值将是未更新的，导致计算错误。复制确保了在每次迭代时，我们都有正确的前一状态的数据，从而可以准确计算当前状态。直接使用`dp`数组会导致计算过程中数据的覆盖，使得无法正确反映前一状态的信息。