<jupyter_start><jupyter_text>说明：    给你一个整数 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、1 <= n <= 50<jupyter_code>class Solution:
    def countVowelStrings(self, n: int) -> int:
        vowels = [0, 1, 2, 3, 4]
        dp = [1] * 5
        if n == 1: 
            return sum(dp)
        idx = 1
        while idx < n:
            pass
            idx += 1
        return sum(dp)
# 超时
class Solution:
    def countVowelStrings(self, n: int) -> int:
        arr = [0, 1, 2, 3, 4]
        self.res = 0
        self.dfs(arr, n, [])
        return self.res
    
    def dfs(self, arr, n, path):
        if n == 0:
            self.res += 1
            return
        for i in range(len(arr)):
            if not path or arr[i] >= path[-1]:
                path.append(arr[i])
                self.dfs(arr[max(i-1, 0):], n - 1, path)
                path.pop()

# 超时
class Solution:
    def countVowelStrings(self, n: int) -> int:
        dp = [0] * (n * 5)
        for i in range(1, n):
            for j in range(5):
                idx = i * 5 + j
                end = i * 5 
                for k in range(idx-5, end):
                    dp[idx] += dp[k]
                dp[idx] -= 1
        return sum(dp[-5:])
solution = Solution()
solution.countVowelStrings(50)
# 3 35
# 4 70
# 5 126<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.15923207227555053, 'fraction_numerical': 0.0378317334839074, 'mean_word_length': 1.4576976421636616, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '122028', 'license': 'Apache-2.0', 'n_tokens_mistral': 819, 'n_tokens_neox': 798, 'n_words': 184, 'path': 'Dynamic Programming/1102/1641. Count Sorted Vowel Strings.ipynb', 'repo_name': 'YuHe0108/Leetcode', 'size': '1771'}