Java实现 LeetCode 552 学生出勤记录 II（数学转换？还是动态规划？）

红太狼 2023-05-28 11:12 28阅读 0赞

## 552. 学生出勤记录 II ##

给定一个正整数 n，返回长度为 n 的所有可被视为可奖励的出勤记录的数量。 答案可能非常大，你只需返回结果mod 109 + 7的值。

学生出勤记录是只包含以下三个字符的字符串：

‘A’ : Absent，缺勤  
‘L’ : Late，迟到  
‘P’ : Present，到场  
如果记录不包含多于一个’A’（缺勤）或超过两个连续的’L’（迟到），则该记录被视为可奖励的。

示例 1:

输入: n = 2  
输出: 8  
解释：  
有8个长度为2的记录将被视为可奖励：  
“PP” , “AP”, “PA”, “LP”, “PL”, “AL”, “LA”, “LL”  
只有"AA"不会被视为可奖励，因为缺勤次数超过一次。  
注意：n 的值不会超过100000。

先附上大佬用数学方法做的：  
用数组放入关系，太顶了  
下面才是我写的勉强过关的代码

class Solution { 
       public int checkRecord(int n) { 
    		long[][] a = new long[][]{ { 1},{ 1},{ 0},{ 1},{ 0},{ 0}};
    		long[][] aMatrix = 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}};
    		while (n>0) { 
    			int m = n & 1;
    			if (m == 1) { 
    				a = this.multipleMatrix(aMatrix, a);
    			}
    			aMatrix = this.multipleMatrix(aMatrix, aMatrix);
    			n = n>>1;
    		}
    		/** * 0 A0L0 * 1 A0L1 * 2 A0L2 * 3 A1L0 * 4 A1L1 * 5 A1L2 */
    		return (int)a[3][0];
    
    	}
    	public long[][] multipleMatrix(long[][] a,long[][] b) { 
    		long mod = (long)1e9+7;
    		long c[][] = new long[a.length][b[0].length];
    		for (int i = 0; i < a.length; i++) { 
    			for (int j = 0; j < b[i].length; j++) { 
    				for (int k = 0; k < a[i].length; k++) { 
    					c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
    				}
    			}
    		}
    		return c;
    	}
    }

class Solution { 
        long M = 1000000007;
        public int checkRecord(int n) { 
            long[] f = new long[n <= 5 ? 6 : n + 1];
            f[0] = 1;
            f[1] = 2;
            f[2] = 4;
            f[3] = 7;
            //四种情况下，我前三个可奖励，我最后一个是l是p无所谓
            //如果中间出现两个LL，那么我必定无效
            //2*f[i-1]和一个-f[i-4]
            for (int i = 4; i <= n; i++)
                f[i] = ((2 * f[i - 1]) % M + (M - f[i - 4])) % M;
            long sum = f[n];
            for (int i = 1; i <= n; i++) { 
                sum += (f[i - 1] * f[n - i]) % M;
            }
            return (int)(sum % M);
        }
     
    }