leetcode-每日一题2022.1.17 统计元音字母序列的数目

题目

力扣

思路一 动态规划

根据每个字母后能接的字母来递推，思路很简单。

代码一

class Solution {
public:
    int mod=1000000007;
    int countVowelPermutation(int n) {
        if(n==1) return 5;
        if(n==2) return 10;
        vector<vector<int>> dp(n+1,vector<int>(5));
        dp[2]={1,2,4,2,1};
        for(int i=3;i<=n;i++){
            dp[i][0]=dp[i-1][1]%mod;
            dp[i][1]=(dp[i-1][0]+dp[i-1][2])%mod;
            dp[i][2]=((dp[i-1][0]+dp[i-1][1])%mod+(dp[i-1][3]+dp[i-1][4])%mod)%mod;
            dp[i][3]=(dp[i-1][2]+dp[i-1][4])%mod;
            dp[i][4]=dp[i-1][0]%mod;
        }
        int sum=0;
        for(int i=0;i<5;i++)
            sum=(sum+dp[n][i])%mod;
        return sum;
    }
};

优化版

因为我们只需要最后一次dp的结果，前面的结果不需要保存，只需要保存上一次dp的结果，可以节省内存占用空间。

class Solution {
public:
    int mod=1000000007;
    int countVowelPermutation(int n) {
        vector<int> dp(5,1),ndp(5);
        while(--n){
            ndp[0]=dp[1];
            ndp[1]=(dp[0]+dp[2])%mod;
            ndp[2]=((dp[0]+dp[1])%mod+(dp[3]+dp[4])%mod)%mod;
            ndp[3]=(dp[2]+dp[4])%mod;
            ndp[4]=dp[0];
            dp=ndp;
        }
        int sum=0;
        for(int x:dp)
            sum=(sum+x)%mod;
        return sum;
    }
};

思路二  矩阵快速幂

根据上面的规律，可以把ndp和dp的转换关系写成矩阵的形式。相乘n次又可以转换成快速幂的形式。

代码二

class Solution {
public:
    int mod=1e9+7;
    vector<vector<long>> mul(vector<vector<long>>& a,vector<vector<long>>& b){
        int r=a.size(),c=b[0].size(),z=b.size();
        vector<vector<long>> ans(r,vector<long>(c));
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                for(int k=0;k<z;k++){
                    ans[i][j]+=(a[i][k]*b[k][j])%mod;
                    ans[i][j]%=mod;
                }
            }
        }
        return ans;
    }
    int countVowelPermutation(int n) {
        vector<vector<long>> cur={{1},{1},{1},{1},{1}};
        vector<vector<long>> mat={{0,1,0,0,0},
                                 {1,0,1,0,0},
                                 {1,1,0,1,1},
                                 {0,0,1,0,1},
                                 {1,0,0,0,0}};
        n--;
        while(n){
            if(n&1) cur=mul(mat,cur);
            mat=mul(mat,mat);
            n=n>>1;
        }
        int sum=0;
        for(int i=0;i<5;i++)
            sum=(sum+cur[i][0])%mod;
        return sum;
    }
};