[刷题防痴呆] 0552 - 学生出勤记录 II (Studen

题目地址

https://leetcode.com/problems/student-attendance-record-ii/

题目描述

552. Student Attendance Record II

An attendance record for a student can be represented as a string where each character signifies whether the student was absent, late, or present on that day. The record only contains the following three characters:

'A': Absent.
'L': Late.
'P': Present.
Any student is eligible for an attendance award if they meet both of the following criteria:

The student was absent ('A') for strictly fewer than 2 days total.
The student was never late ('L') for 3 or more consecutive days.
Given an integer n, return the number of possible attendance records of length n that make a student eligible for an attendance award. The answer may be very large, so return it modulo 109 + 7.

 

Example 1:

Input: n = 2
Output: 8
Explanation: There are 8 records with length 2 that are eligible for an award:
"PP", "AP", "PA", "LP", "PL", "AL", "LA", "LL"
Only "AA" is not eligible because there are 2 absences (there need to be fewer than 2).
Example 2:

Input: n = 1
Output: 3
Example 3:

Input: n = 10101
Output: 183236316

思路

• dfs会超时. dfs + 记忆化搜索.
• 注意, absent往下传的时候要把late清零.
• dp.
• 注意, dp的时候数组最好init为long, 因为中间有可能数据过大, 结果返回转回int.

关键点

代码

• 语言支持：Java

// dfs会超时
class Solution {
    
    int mod = 1000000007;

    public int checkRecord(int n) {
        return dfs(0, 0, 0, n);
    }

    private int dfs(int day, int absent, int late, int n) {
        if (day >= n) {
            return 1;
        }
        int ans = 0;
        ans = (ans + dfs(day + 1, absent, 0, n)) % mod;
        if (absent < 1) {
            ans = (ans + dfs(day + 1, 1, 0, n)) % mod;
        }
        if (late < 2) {
            ans = (ans + dfs(day + 1, absent, late + 1, n)) % mod;
        }
        return ans;
    }
}


// dfs + 记忆化搜索
class Solution {
     int mod = 1000000007;
    public int checkRecord(int n) {
        int[][][] memo = new int[n][2][3];
        return dfs(0, 0, 0, n, memo);
    }

    private int dfs(int day, int absent, int late, int n, int[][][] memo) {
        if (day >= n) {
            return 1;
        }

        if (memo[day][absent][late] != 0) {
            return memo[day][absent][late];
        }
        int ans = 0;
        ans = (ans + dfs(day + 1, absent, 0, n, memo)) % mod;
        if (absent < 1) {
            ans = (ans + dfs(day + 1, 1, 0, n, memo)) % mod;
        }
        if (late < 2) {
            ans = (ans + dfs(day + 1, absent, late + 1, n, memo)) % mod;
        }

        memo[day][absent][late] = ans;
        return ans;
    }
}

// dp
class Solution {

    int mod = 1000000007;
    public int checkRecord(int n) {
        long[][][] dp = new long[n][2][3];
        dp[0][0][0] = 1;
        dp[0][1][0] = 1;
        dp[0][0][1] = 1;

        for (int i = 1; i < n; i++) {
            dp[i][0][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]) % mod;
            dp[i][1][0] = (dp[i - 1][1][0] + dp[i - 1][1][1] + dp[i - 1][1][2]) % mod;

            dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]) % mod;
            dp[i][0][1] = dp[i - 1][0][0];
            dp[i][0][2] = dp[i - 1][0][1];
            dp[i][1][1] = dp[i - 1][1][0];
            dp[i][1][2] = dp[i - 1][1][1];
        }

        long ans = 0;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                ans = (ans + dp[n - 1][i][j]) % mod;
            }
        }

        return (int) ans;
    }
}