[数据结构与算法]「LeetCode」学生出勤记录 II 动态规划｜矩阵快速幂

解法1: dp[ i ][ j ][ k ] 表示枚举到第 i 天时恰好有 j 次迟到 k 次缺勤时的方案数，时间复杂度 O（n）

class Solution:
    def checkRecord(self, n: int) -> int:
        mod=10**9+7
        dp=[[[0]*2 for j in range(3)] for i in range(n+1)]
        dp[0][0][0]=1
        for i in range(1,n+1):
            for j in range(3):
                for k in range(2):
                    if j==0:
                        dp[i][j][k]=dp[i-1][0][k]+dp[i-1][1][k]+dp[i-1][2][k]
                        if k-1>=0:
                            dp[i][j][k]+=dp[i-1][0][k-1]+dp[i-1][1][k-1]+dp[i-1][2][k-1]
                        dp[i][j][k]%=mod
                    else:
                        dp[i][j][k]=dp[i-1][j-1][k]%mod
        ans=0
        for i in range(3):
            for j in range(2):
                ans+=dp[-1][i][j]
        return ans%mod

?

?解法 2:同解法1，但因为第 i 天的方案数只和第 i-1 天，所以可以考虑滚动第一维,时间复杂度 O(n) ，但增加了缓存命中率，所以要比解法 1 快一些

class Solution:
    def checkRecord(self, n: int) -> int:
        mod=10**9+7
        dp=[[[0]*2 for j in range(3)] for i in range(2)]
        dp[0][0][0]=1
        for i in range(1,n+1):
            for j in range(3):
                for k in range(2):
                    if j==0:
                        dp[i&1][j][k]=dp[(i-1)&1][0][k]+dp[(i-1)&1][1][k]+dp[(i-1)&1][2][k]
                        if k-1>=0:
                            dp[i&1][j][k]+=dp[(i-1)&1][0][k-1]+dp[(i-1)&1][1][k-1]+dp[(i-1)&1][2][k-1]
                        dp[i&1][j][k]%=mod
                    else:
                        dp[i&1][j][k]=dp[(i-1)&1][j-1][k]%mod
        ans=0
        for i in range(3):
            for j in range(2):
                ans+=dp[n&1][i][j]
        return ans%mod

解法3: 考虑使用矩阵乘法配合快速幂来提高转移效率，时间复杂度 O(logn)

class Solution {
    public static final int MOD=1000000007;

    public long[][] mul(long[][] a,long[][] b){
        int n=a.length;
        int m=b[0].length;
        assert a[0].length==b.length;
        long[][] ans=new long[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                for(int k=0;k<a[0].length;k++){

                    ans[i][j]+=a[i][k]*b[k][j]%MOD;
                    ans[i][j]%=MOD;
                }
            }
        }
        return ans;
    }

    public long[][] quickPow(long[][] x,int n){
        int m=x.length;
        long[][] ans=new long[m][m];
        for(int i=0;i<m;i++)
            ans[i][i]=1;
        while(n>0){
            if((n&1)!=0)
                ans=mul(ans,x);
            x=mul(x,x);
            n>>=1;
        }
        return ans;
    }

    public int checkRecord(int n) {
        long[][] ans=new long[][]{{1},{0},{0},{0},{0},{0}};
        long[][] base=new long[][]{
            {1,1,1,0,0,0},
            {1,0,0,0,0,0},
            {0,1,0,0,0,0},
            {1,1,1,1,1,1},
            {0,0,0,1,0,0},
            {0,0,0,0,1,0}
        };
        long[][] buf=quickPow(base,n);
        ans=mul(buf,ans);
        int res=0;
        for(int i=0;i<ans.length;i++){
            for(int j=0;j<ans[0].length;j++){
                res+=ans[i][j];
                res%=MOD;
            }
        }
        return res;
    }
}

?