1220.-count-vowels-permutation.md

1220. Count Vowels Permutation

用前面i-1的个数推到 ith 的个数


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        '''
        a - > e 
        e - > a i 
        i - > a , e , u , o 
        o - > i,u
        u - > a 
        
        转过来
        a e i o u 
        a,0 <- 1,2,4
        e 1<- 0,2
        
        '''
        mod = 10 ** 9 + 7
        
        f = [[0] * 5 for _ in range(n)]
        f[0] = [1,1,1,1,1]
        
        for i in range(1, n):
            f[i][0] = (f[i - 1][1]+ f[i - 1][2] + f[i-1][4])%mod
            f[i][1] = (f[i - 1][0] + f[i - 1][2])%mod
            f[i][2] = (f[i - 1][1] + f[i - 1][3])%mod
            f[i][3] = (f[i - 1][2])%mod
            f[i][4] = (f[i - 1][2] + f[i - 1][3])%mod
            
        return sum(f[-1]) % mod