# 552. Student Attendance Record II

### Latest:

```java
class Solution {
    public int checkRecord(int n) {
        Integer[][][] memo = new Integer[n][2][3];
        return dfs(n, 0, 0, 0, memo);
    }
    private int dfs(int n, int i, int absentCount, int lateCount, Integer[][][] memo) {
        if (absentCount >= 2 || lateCount >= 3) {
            return 0;
        }

        if (i == n) {
            return 1;
        }
        if (memo[i][absentCount][lateCount] != null) {
            return memo[i][absentCount][lateCount];
        }
        // choose P, so no L only choose L can have consecutive case, a remain original value
        long result = dfs(n, i+1, absentCount, 0, memo);

        // choose A, so no L only choose L can have consecutive case, A+1
        result += dfs(n, i+1, absentCount+1, 0, memo);
        
        // choose L
        // only choose L can have consecutive case, so lateCount can +1
        result += dfs(n, i+1, absentCount, lateCount+1, memo);
        
        return memo[i][absentCount][lateCount] = (int)(result%(1_000_000_007));
    }
}

/***

A count < 2
L consecutive count < 3

[i][a count][l c count]
n.   3.        0 1     0 1 2

l = 0


how to handle " consecutive days."?

-> consecutive call dfs!
so other 2 DFS, l = 0
we only increase l count in consecutive call (means in the same DFS), other dfs give them l = 0


T: O(n*2*3) = O(n)
S: O(n)

practice, if I want all combinations count?? without any restrictions
    private int dfsTest(int n, int i) {
        if (i == n) {
            return 1;
        }
        int result = 0;
        for (int c = 0; c < 3; c++) {
            result += dfsTest(n, i+1); //if no restrctions: f(n) = A(n-1) + L(n-1) + P(n-1) -> means for loop 3 times
        }
        return result;
    }

    or can write like this, the same position we can have 3 different choices, A or L or P
    // A
    result += dfsTest(n, i+1);
    // L
    result += dfsTest(n, i+1);
    // P
    result += dfsTest(n, i+1);

so if there are restrictions, need to add restrictions in these 3 DFS:

        // choose P, so no L only choose L can have consecutive case, a remain original value
        long result = dfs(n, i+1, absentCount, 0, memo);

        // choose A, so no L only choose L can have consecutive case, A+1
        result += dfs(n, i+1, absentCount+1, 0, memo);
        
        // choose L
        // only choose L can have consecutive case, so lateCount can +1
        result += dfs(n, i+1, absentCount, lateCount+1, memo);

 */
```

For all combinations: idea is here:

{% embed url="<https://leetcode.com/playground/AmueBuEb>" %}

refer to:

<https://leetcode.com/problems/student-attendance-record-ii/discuss/650804/Evolve-from-brute-force-to-optimal>

and this

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

## DFS + memo

T : O(n), it's memoized to O(TOTAL \* A \* L), since A and L have fixed number which is 2 and 3, then the complexity becomes, O(TOTAL) = O(N)

S: O(n)

```java
class Solution {
    public int checkRecord(int n) {
        Integer[][][] memo = new Integer[n][2][3];
        return dfs(0, 0, 0, n, memo);
    }
    private int dfs(int i, int a, int l, int n, Integer[][][] memo) {
        if (i == n) {
            return 1; // one possiple result
        }
        if (memo[i][a][l] != null) {
            return memo[i][a][l];
        }
        // present 時, L 給 0, 可以保證 L 不連續, a 照傳, 因為不需要判斷連續幾個
        long res = dfs(i+1, a, 0, n, memo);
        
        // absent 時, L 給 0, 可以保證 L 不連續, a 照傳, 因為不需要判斷連續幾個
        if (a == 0) { // a <= 1, so 只有 a == 0 才能多加1
            res += dfs(i+1, a+1, 0, n, memo);
        } 
        
        // handle for consecutive, so l = 0 or 1 we can add one more l, 這樣就可以不連續！！！
        // 搭配之前兩個 L = 0, 可以保證不連續
        if (l < 2) { 
            res += dfs(i+1, a, l+1, n, memo);
        }
        memo[i][a][l] = (int)(res%1000000007) ;
        return memo[i][a][l];
    }
}

/*
The student was absent ('A') for strictly fewer than 2 days total. so legal is 0,1
The student was never late ('L') for 3 or more consecutive days. so legal is 0,1,2
*/

/*
return the "number" of possible attendance records of length n that make a student eligible for an attendance award.

A A
L L
P P


3*3 = 9


3^n => 排除 count(A) = 2, LLL

but A only one time, so time cpomplexty => 2^n

use memo => O(n)
*/
```

## another one

```java
class Solution {
    public int checkRecord(int n) {
        Integer[][][] memo = new Integer[n][2][3];
        return dfs(0, 0, 0, n, memo);
    }
    private int dfs(int i, int a, int l, int n, Integer[][][] memo) {
    // 注意這要在最前面, 不然有些狀況會過濾不到
    // 因為照理是 call dfs 前就要判斷 
        if (a >= 2 || l >= 3) { 
            return 0;
        }
        if (i == n) {
            return 1;
        }

        if (memo[i][a][l] != null) {
            return memo[i][a][l];
        }
        long res = dfs(i+1, a, 0, n, memo); // present
        res += dfs(i+1, a+1, 0, n, memo); // Absent
        res += dfs(i+1, a, l+1, n, memo); // Late
        
        memo[i][a][l] = (int)(res%1000000007);
        return memo[i][a][l];
    }

}

```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/552.-student-attendance-record-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.