[DP ]1220. Count Vowels Permutation

해설 : 이전 dp 문제들과 같이  현재 단계에서의 만들수 있는 경우의 수는 

이전 단계의 a,e,i,o,u를 사용해서 만들 수 있는 경우의 합과 같다. 

따라서 dp[0][0] (=a) , dp[0][1] (=e) 은 미리 구해놓고, 

dp[1][0] 에서는 조건들에 따라 수를 합해 나가면된다. 

 

 

class Solution {
public:
    int countVowelPermutation(int n) {
        long long modulo = 1000000007;
        
        vector<vector<long long>> dp(n, vector<long long> (5, 0));        
        for(int i=0; i<5; ++i){
            dp[0][i]=1;
        }
        
        for(int j =1; j<n; j++){
            dp[j][0] += (dp[j-1][1]) %modulo;
            dp[j][1] += (dp[j-1][0] + dp[j-1][2])%modulo;
            dp[j][2] += (dp[j-1][0] + dp[j-1][1] + dp[j-1][3] + dp[j-1][4])%modulo;
            dp[j][3] += (dp[j-1][2] + dp[j-1][4])%modulo;
            dp[j][4] += (dp[j-1][0])%modulo;          
        }
        
        long long sum = 0;
        for(int i=0; i<5; ++i){
            sum += dp[n-1][i];
        }
        
        return sum%modulo;
        
    }
};