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

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

Image of Datadog

The Future of AI, LLMs, and Observability on Google Cloud

Datadog sat down with Googleโ€™s Director of AI to discuss the current and future states of AI, ML, and LLMs on Google Cloud. Discover 7 key insights for technical leaders, covering everything from upskilling teams to observability best practices

Learn More

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more