Участник:ArtemTovkes/count-vowels-permutation

Материал из DISCOPAL
Перейти к: навигация, поиск

Python3

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

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        mod = 10 ** 9 + 7
        followRules = [[1], [0, 2], [0, 1, 3, 4], [2, 4], [0]]
        dp = [1] * 5
 
        for step in range(n - 1):
            dp2 = [0] * 5
            for vowel, count in enumerate(dp):
                for nextV in followRules[vowel]:
                    dp2[nextV] += count
                    dp2[nextV] %= mod
            dp = dp2
        return sum(dp) % mod