统计元音字母序列的数目

• 解题思路
• • 动态规划
  • 复杂度

力扣链接

解题思路

官方题解

• 动态规划
  这题的动态规划的转移方程非常容易看出,还有就是要处理下溢出问题
  

动态规划

class Solution {
    public int countVowelPermutation(int n) {
        int mod = 1000000007;
        long p1 = 1;
        long p2 = 1;
        long p3 = 1;
        long p4 = 1;
        long p5 = 1;
        for (int i = 2; i <= n; ++i) {
            long t1 = p1;
            long t2 = p2;
            long t3 = p3;
            long t4 = p4;
            long t5 = p5;
            
            p1 = (t2 + t3 + t5) % mod;
            p2 = (t1 + t3) % mod;
            p3 = (t2 + t4) % mod;
            p4 = t3 % mod;
            p5 = (t3 + t4) % mod;
        }

        long sum = 0;
        sum = (sum + p1) % mod;
        sum = (sum + p2) % mod;
        sum = (sum + p3) % mod;
        sum = (sum + p4) % mod;
        sum = (sum + p5) % mod;
        return (int) sum;
    }
}

复杂度

• 时间复杂度: O(C * n)
• 空间复杂度: O©