Description

Submission

class Solution {
public:
    int countVowelPermutation(int n) {
        vector<vector<long long>> dp(5, vector<long long>(n));
        // unordered_map<char, int> Map {{'a', 0}, {'e', 1}, {'i', 2}, {'o', 3}, {'u', 4}};
        const int M = 1e9 + 7;

        dp[0][0] = dp[1][0] = dp[2][0] = dp[3][0] = dp[4][0] = 1;
        for(int i = 1; i < n; ++i) {
            dp[0][i] = dp[1][i-1];
            dp[1][i] = (dp[0][i-1] + dp[2][i-1]) % M;
            dp[2][i] = (dp[0][i-1] + dp[1][i-1] + dp[3][i-1] + dp[4][i-1]) % M;
            dp[3][i] = (dp[2][i-1] + dp[4][i-1]) % M;
            dp[4][i] = dp[0][i-1];
        }

        long long ret = 0;

        for(int i = 0; i < 5; ++i) {
            ret = (ret+ dp[i][n-1]) % M;
        }

        return ret;
    }
};