leetcode

commit ab2acb5877703b508c92587a52a6e3d711d2e777
parent 0f0efc725350972d6bee80b4c2a0927bf923f3dd
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 26 May 2024 13:33:39 +0200

Daily Problem

Diffstat:
A
Problems/0552.cpp
 | 
19
+++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 20 insertions(+), 0 deletions(-)
diff --git a/Problems/0552.cpp b/Problems/0552.cpp
@@ -0,0 +1,19 @@
+class Solution {
+    static const int MOD = 1e9 + 7;
+    static int dp[2][3][100001];
+
+  public:
+    Solution() { memset(dp, 0xFF, sizeof(dp)); }
+    int checkRecord(int n, int a = 0, int l = 0) const {
+        if (n == 0) return 1;
+        if (dp[a][l][n] != -1) return dp[a][l][n];
+
+        int res = checkRecord(n - 1, a, 0);
+        if (l < 2) res = (res + checkRecord(n - 1, a, l + 1)) % MOD;
+        if (a < 1) res = (res + checkRecord(n - 1, a + 1, 0)) % MOD;
+
+        return dp[a][l][n] = res;
+    }
+};
+
+int Solution::dp[2][3][100001];
diff --git a/README.md b/README.md
@@ -384,6 +384,7 @@ for solving problems.
 |  0543  |    Easy    | [Diameter of Binary Tree](Problems/0543.cpp)                                                       |
 |  0547  |   Medium   | [Number of Provinces](Problems/0547.cpp)                                                           |
 |  0550  |   Medium   | [Game Play Analysis IV](Problems/0550.cpp)                                                         |
+|  0552  |    Hard    | [Student Attendance Record II](Problems/0552.cpp)                                                  |
 |  0553  |   Medium   | [Optimal Division](Problems/0553.cpp)                                                              |
 |  0554  |   Medium   | [Brick Wall](Problems/0554.cpp)                                                                    |
 |  0556  |   Medium   | [Next Greater Element III](Problems/0556.cpp)                                                      |