1220. Count Vowels Permutation

https://leetcode.com/problems/count-vowels-permutation/

Python

Top Down DP

• 真實世界在寫的話，用來當開頭的#要小心另外處理

from functools import cache


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        rules = {
            '#': 'aeiou',
            'a': 'eiu',
            'e': 'ai',
            'i': 'eo',
            'o': 'i',
            'u': 'io',
        }

        @cache
        def dp(lead, remains):
            if remains == 0:
                return 1

            if lead not in rules:
                return 0

            count = 0
            for vow in rules[lead]:
                count += dp(vow, remains-1)
            return count

        return dp('#', n) % ((10**9)+7)