leetcode 统计元音字母序列的数目 -- 排列组合递推问题

给你一个整数 n，请你帮忙统计一下我们可以按下述规则形成多少个长度为n的字符串：

字符串中的每个字符都应当是小写元音字母（'a', 'e', 'i', 'o', 'u'）
每个元音 'a' 后面都只能跟着 'e'
每个元音 'e' 后面只能跟着'a'或者是'i'
每个元音 'i'后面不能再跟着另一个'i'
每个元音'o'后面只能跟着'i' 或者是'u'
每个元音'u'后面只能跟着 'a'
由于答案可能会很大，所以请你返回模 10^9 + 7之后的结果。

示例1

输入：n = 1
输出：5
解释：所有可能的字符串分别是："a", "e", "i" , "o" 和 "u"。

示例2

输入：n = 2
输出：10
解释：所有可能的字符串分别是："ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" 和 "ua"。

示例3

输入：n = 5
输出：68

提示

1 <= n <= 2 * 10^4

这道题的想法就是计算当有1到n个字符时，字符串可能的组成种数。由于字符串只能由a、e、i、 o、 u组成，令k表示当前计算的字符串的长度，a[k][0]表示字符串长度为k时，第k个字符为a的字符串组成种数。以此类推，a[k][1]表示第k个字符为e的字符串组成种数，a[k][2]为i的组成种数，a[k][3]为o的组成种数，a[k][4]为u的组成种数。

由给定的规则知，如果第k个字符要为a时，则第k-1个字符只能为e、i、u ，因此第k个字符为a的字符串组成种数即为第k-1个字符为e、i、u时的字符串组成种数，即a[k][0] = a[k-1][1]+a[k-1][2]+a[k-1][4]。当第k个字符为e、i、 o、 u的情况可以依次类推。

一开始我没有取模，报数字溢出错误。google了一下，看到这篇文章说在进行加法时取模不会影响最后地结果，就大胆地取模了。

class Solution {
public:
    int countVowelPermutation(int n) {
        int M = pow(10,9)+7;
        vector<vector<long long int>> a(n);
        for(int i=0;i<n;i++){
            a[i].resize(5);
        }
        for(int i=0;i<5;i++){
            a[0][i] = 1;
        }
        for(int i=0;i<n-1;i++){
            a[i+1][0] = (a[i][1]+a[i][2]+a[i][4]) % M;
            a[i+1][1] = (a[i][0]+a[i][2]) % M;
            a[i+1][2] = (a[i][1]+a[i][3]) % M;
            a[i+1][3] = (a[i][2]) % M;
            a[i+1][4] = (a[i][2]+a[i][3])%M;
        }
        return (a[n-1][0]+a[n-1][1]+a[n-1][2]+a[n-1][3]+a[n-1][4])%M;
    }
};

题目链接：https://leetcode.com/contest/weekly-contest-157/problems/count-vowels-permutation/

最后编辑于：2019.10.21 10:11:53