552. Student Attendance Record II

Latest:

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:

Playground - LeetCodeLeetCode

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)

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

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];
    }

}