552. 学生出勤记录 II.md

问题描述

给定一个正整数 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。

问题分析

记录第i次出勤的五种能获得奖励的状态:

1. 出席，总共缺席0次
2. 出席，总共缺席1次
3. 迟到，总共缺席0次，且连续迟到1次
4. 迟到，总共缺席0次，且连续迟到2次
5. 迟到，总共缺席1次，且连续迟到1次
6. 迟到，总共缺席1次，且连续迟到2次
7. 缺席，总共缺席1次.

然后根据上面的状态，画出状态转移的自动机， 然后就很清晰了！！ （下图只是参考，状态转移不难画。。

# define mod 1000000007
# define add(a,b) (a+b)%1000000007
class Solution {
public:
    int checkRecord(int n) {
        int dp[100010][4][2]={0};
        // 0是出席， 1是迟到且连续迟到1次, 2是迟到且连续迟到2次， 3是缺勤
        dp[1][0][0] = dp[1][1][0] = dp[1][3][1] = 1;
        
        
        for ( int i=2; i<=n; ++i ){
            // 这次出席了
            //dp[i][0][0] = (dp[i-1][1][0] + dp[i-1][2][0] + dp[i-1][0][0])%mod;
            dp[i][0][0] = add(dp[i-1][1][0] ,add( dp[i-1][2][0] , dp[i-1][0][0]));
            
            //dp[i][0][1] = (dp[i-1][1][1] + dp[i-1][2][1] + dp[i-1][0][1] + dp[i-1][3][1])%mod;
            dp[i][0][1] = add(add(dp[i-1][1][1] , dp[i-1][2][1]) , add(dp[i-1][0][1] , dp[i-1][3][1]));
            
            // 这次迟到了
            dp[i][1][0] = dp[i-1][0][0];
            //dp[i][1][1] = (dp[i-1][0][1] + dp[i-1][3][1])%mod;
            dp[i][1][1] = add(dp[i-1][0][1] , dp[i-1][3][1]); 
            
            dp[i][2][0] = dp[i-1][1][0];
            dp[i][2][1] = dp[i-1][1][1];
            
            // 这次缺席了
            dp[i][3][1] = add(dp[i-1][2][0] ,add( dp[i-1][0][0] , dp[i-1][1][0]));
        }
        return add( add(dp[n][0][0] , dp[n][0][1]) ,add(dp[n][1][0] ,add( dp[n][1][1] ,add( dp[n][2][1],add( dp[n][2][0] ,dp[n][3][1])))));
    }
};

可以滚动数组一下，把空间优化到常数

# define mod 1000000007
# define add(a,b) (a+b)%1000000007
class Solution {
public:
    // 画个状态机就成easy题了..
    int checkRecord(int n) {
        int dp[4][2]={0};
        int cur[4][2]={0};
        // 0是出席， 1是迟到且连续迟到1次, 2是迟到且连续迟到2次， 3是缺勤
        
        // 初始化
        dp[0][0] = dp[1][0] = dp[3][1] = 1;
        
        for ( int i=2; i<=n; ++i ){
            // 这次出席了
            cur[0][0] = add(dp[1][0] ,add( dp[2][0] , dp[0][0]));
            cur[0][1] = add(add(dp[1][1] , dp[2][1]) , add(dp[0][1] , dp[3][1]));
            
            // 这次迟到了
            // 连续1次迟到
            cur[1][0] = dp[0][0];
            cur[1][1] = add(dp[0][1] , dp[3][1]); 
            
            // 连续2次迟到
            cur[2][0] = dp[1][0];
            cur[2][1] = dp[1][1];
            
            // 这次缺席了
            cur[3][1] = add(dp[2][0] ,add( dp[0][0] , dp[1][0]));
            swap(cur, dp);
        }
        return add( add(dp[0][0] , dp[0][1]) ,add(dp[1][0] ,add( dp[1][1] ,add( dp[2][1],add( dp[2][0] ,dp[3][1])))));
    }
};