每日一题(2022-01-18):统计元音字母序列的数目

每日一题(2022-01-18):统计元音字母序列的数目

来源:力扣
难度:困难
题目:1220. 统计元音字母序列的数目

题目详情

原题截图.png

题解思路

动态规划问题还是一如既往地投翔,不过看过题解之后发现理解起来也并不困难,这次基本上是照搬答案了,需要注意的是使用long long存储临时变量:
官方题解.png

代码结果

class Solution {
public:
    int countVowelPermutation(int n) {
       static const long long mod = 1e9 + 7;
        vector<long long> dp(5, 1);
        vector<long long> ndp(5);
        for (int i = 2; i <= n; ++i) {
            /* a前面可以为e,u,i */
            ndp[0] = (dp[1] + dp[2] + dp[4]) % mod;
            /* e前面可以为a,i */
            ndp[1] = (dp[0] + dp[2]) % mod;
            /* i前面可以为e,o */
            ndp[2] = (dp[1] + dp[3]) % mod;
            /* o前面可以为i */
            ndp[3] = dp[2];
            /* u前面可以为i,o */
            ndp[4] = (dp[2] + dp[3]) % mod;
            dp = ndp;
        }
        return accumulate(dp.begin(), dp.end(), 0LL) % mod;
    }
};

运行结果.png