DEV Community

Cover image for ๐—ง๐—ต๐—ฒ ๐—™๐—ถ๐—ฟ๐˜€๐˜ ๐—ฆ๐˜๐—ฟ๐—ฒ๐—ฎ๐—ธ ๐—ผ๐—ป ๐—Ÿ๐—ฒ๐—ฒ๐˜๐—–๐—ผ๐—ฑ๐—ฒ
Pranjal Sailwal
Pranjal Sailwal

Posted on

๐—ง๐—ต๐—ฒ ๐—™๐—ถ๐—ฟ๐˜€๐˜ ๐—ฆ๐˜๐—ฟ๐—ฒ๐—ฎ๐—ธ ๐—ผ๐—ป ๐—Ÿ๐—ฒ๐—ฒ๐˜๐—–๐—ผ๐—ฑ๐—ฒ

Dynamic Programming- Q 552. Student Attendance Record II

class Solution {
    public int checkRecord(int n) {
        final int MOD = 1000000007;
        int[][] dpCurrState = new int[2][3];
        int[][] dpNextState = new int[2][3];
        dpCurrState[0][0] = 1;
        for (int len = 0; len < n; len++) {
            for (int i = 0; i < 2; i++) {
                Arrays.fill(dpNextState[i], 0);
            }
            for (int totalAbsences = 0; totalAbsences < 2; totalAbsences++) {
                for (int consecutiveLates = 0; consecutiveLates < 3; consecutiveLates++) {
                    dpNextState[totalAbsences][0] = (dpNextState[totalAbsences][0] + dpCurrState[totalAbsences][consecutiveLates]) % MOD;
                    if (totalAbsences < 1) {
                        dpNextState[totalAbsences + 1][0] = (dpNextState[totalAbsences + 1][0] + dpCurrState[totalAbsences][consecutiveLates]) % MOD;
                    }       
                    if (consecutiveLates < 2) {
                        dpNextState[totalAbsences][consecutiveLates + 1] = (dpNextState[totalAbsences][consecutiveLates + 1] + dpCurrState[totalAbsences][consecutiveLates]) % MOD;
                    }
                }
            }   
            for (int i = 0; i < 2; i++) {
                System.arraycopy(dpNextState[i], 0, dpCurrState[i], 0, 3);
            }
        }
        int totalCount = 0;
        for (int totalAbsences = 0; totalAbsences < 2; totalAbsences++) {
            for (int consecutiveLates = 0; consecutiveLates < 3; consecutiveLates++) {
                totalCount = (totalCount + dpCurrState[totalAbsences][consecutiveLates]) % MOD;
            }
        }       
        return totalCount;
    }
}
Enter fullscreen mode Exit fullscreen mode

๐—ข๐—ฝ๐—ฒ๐—ป ๐˜๐—ผ ๐—จ๐—ฝ๐—ฑ๐—ฎ๐˜๐—ฒ๐˜€ ๐—ฎ๐—ป๐—ฑ ๐—ฆ๐˜‚๐—ด๐—ด๐—ฒ๐˜€๐˜๐—ถ๐—ผ๐—ป๐˜€.

Top comments (0)