1220.统计元音字母序列的数目

链接：1220.统计元音字母序列的数目
难度：Hard
标签：动态规划
简介：给你一个整数 n，请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串。

题解 1 - cpp

• 编辑时间：2022-01-17
• 内存消耗：5.8MB
• 编程语言：cpp
• 解法介绍：动态规划，dp[i][j]表示第 i 轮时，j 元音为结尾的数量。

class Solution {
   public:
    int mod = 1e9 + 7;
    int countVowelPermutation(int n) {
        // 0 : a, 1 : e, 2 : i, 3 : o, 4 : u
        // a -> e
        // e -> a i
        // i -> a e o u
        // o -> i u
        // u -> a
        long long dp[2][5];
        for (int i = 0; i < 5; i++) {
            dp[0][i] = 0;
            dp[1][i] = 1;
        }
        for (int i = 2; i <= n; i++) {
            int pidx = (i + 1) % 2;
            int idx = i % 2;
            dp[idx][0] = (dp[pidx][1] + dp[pidx][2] + dp[pidx][4]) % mod;
            dp[idx][1] = (dp[pidx][0] + dp[pidx][2]) % mod;
            dp[idx][2] = (dp[pidx][1] + dp[pidx][3]) % mod;
            dp[idx][3] = dp[pidx][2] % mod;
            dp[idx][4] = (dp[pidx][2] + dp[pidx][3]) % mod;
        }
        long long ans = 0;
        for (int i = 0; i < 5; i++) ans = (ans + dp[n % 2][i]) % mod;
        return ans;
    }
};