# [552. Student Attendance Record II](https://leetcode.com/problems/student-attendance-record-ii/description/?envType=daily-question&envId=2024-05-26) # 1. Tóm tắt đề bài Hồ sơ điểm danh của một sinh viên được biểu diễn bởi một xâu gồm các ký tự: - `A`: Vắng mặt - `L`: Đi muộn - `P`: Đi đúng giờ Một sinh viên đủ điểm chuyên cần nếu sinh viên đó đủ hai điều kiện sau: - Vắng mặt (`A`) **tổng cộng** $< 2$ ngày (hay số ngày vắng tối đa là $1$) - Không bao giờ muộn (`L`) $\ge 3$ ngày **liên tiếp** Cho một số nguyên $n$, hãy trả về số hồ sơ điểm danh dài $n$ ngày đủ điểm chuyên cần. Đáp án có thể rất lớn, vì vậy hãy trả về đáp án $\mathrm{mod} \ 10^9 + 7$. ### Giới hạn $1 \le n \le 10^5$ # 2. Tóm tắt lời giải **Độ phức tạp dự tính: $O(n)$** Một cách để giải bài toán này là ngây thơ xét hết tất cả các xâu hồ sơ điểm danh độ dài $n$. Làm theo cách này, ta sẽ có độ phức tạp thời gian và bộ nhớ $O(3^n)$, chắc chắn là không thể đáp ứng được đối với giới hạn được cho. Ta có thể tối ưu lời giải bằng cách sử dụng **Quy hoạch động** (Dynamic Programming). Gọi $dp[i][absent][late]$ là số hồ sơ đủ điểm chuyên cần có độ dài $i$ với số ngày vắng $absent$ và ở đuôi có chuỗi $late$ ngày muộn liên tiếp. Với một ngày $i$ bất kỳ, ta có 3 trường hợp: - Đi học đúng giờ `P`: Số ngày vắng $absent$ không đổi và chuỗi đi muộn $late$ về lại $0$ - $dp[i][0][0] = \sum^{2}_{late=0}dp[i - 1][0][late]$ - $dp[i][1][0] = \sum^{2}_{late=0}dp[i - 1][1][late]$ - Vắng mặt `A`: Vì số ngày vắng tối đa là $1$, sinh viên chỉ có thể vắng mặt nếu hồ sơ hiện tại chưa có ngày vắng nào - $dp[i][1][0] = dp[i][1][0] + \sum^{2}_{late=0}dp[i - 1][0][late]$ - Đi muộn `L`: Sinh viên chỉ có thể đi muộn nếu sinh viên không đi muộn trong cả 2 ngày trước (hôm nay đi muộn sẽ khiến hồ sơ có 3 ngày đi muộn liên tiếp) - $dp[i][0][1] = dp[i - 1][0][0]$ - $dp[i][0][2] = dp[i - 1][0][1]$ - $dp[i][1][1] = dp[i - 1][1][0]$ - $dp[i][1][2] = dp[i - 1][1][1]$ # 3. Lời giải chi tiết ## Cách 1: 3D DP ### [Code mẫu](https://leetcode.com/problems/student-attendance-record-ii/submissions/1268225680) ### Độ phức tạp thuật toán Thời gian: $O(3 * 2 * n) = O(n)$ Bộ nhớ mở rộng: $O(3 * 2 *n) = O(n)$ ## Cách 2: 3D DP (Tối ưu bộ nhớ) Ta để ý rằng với mỗi hàng $i$ trong $dp[i][absent][late]$, để tính toán được cả hàng, ta chỉ cần dựa vào hàng trước đó $i - 1$. Vì vậy, thay vì lưu một mảng 3 chiều, ta chỉ cần lưu $dp[absent][late]$ và trong vòng lặp $n$ lần, ta [deep copy](https://en.wikipedia.org/wiki/Object_copying#Deep_copy) mảng $dp$ hiện tại vào một mảng $prev$ tạm thời và lưu kết quả tính vào $dp$. ### [Code mẫu](https://leetcode.com/problems/student-attendance-record-ii/submissions/1268236411) ### Độ phức tạp thuật toán Thời gian: $O(3 * 2 * n) = O(n)$ Bộ nhớ mở rộng: $O(3 * 2) = O(1)$ # 4. Kết luận & Gợi ý mở rộng Một bài quy hoạch động thực ra không khó để tìm ra trạng thái và quan hệ truy hồi, tuy nhiên việc xét hết đủ các hệ thức truy hồi sao cho hợp lý hơi rồi não một chút :smile: Một số bài DP 3 chiều mở rộng: - [1335. Minimum Difficulty of a Job Schedule](https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/description/) - [1463. Cherry Pickup II](https://leetcode.com/problems/cherry-pickup-ii/description/)