统计字典序元音字符串的数目

难度

• Easy
• Medium
• Hard

思路

三种做法，暴力、记忆化搜索、动态规划。

DP 做法中，每一步能取的字母，实际上就是小于等于自己的字母，加总即可。

代码

记忆化搜索

class Solution:
    def countVowelStrings(self, n: int) -> int:
        # 记忆化搜索
        @cache
        def dfs(cur_pos, cur_ch):
            nonlocal n
            if cur_pos == n:
                return 1
            return sum([dfs(cur_pos + 1, i) for i in range(cur_ch, 5)])

        return dfs(0, 0)

动态规划

class Solution:
    def countVowelStrings(self, n: int) -> int:
        # 动态规划
        dp = [[0] * 5 for _ in range(n)]
        for i in range(5):
            dp[0][i] = 1
        for i in range(1, n):
            for j in range(5):
                dp[i][j] += sum(dp[i - 1][k] for k in range(j + 1))
        return sum(dp[n - 1][j] for j in range(5))

实践中，记忆化搜索其实就是在暴力的基础上加个 @cache 。