[Google] LeetCode 552 Student Attendance Record II
2022/9/1 6:52:53
本文主要是介绍[Google] LeetCode 552 Student Attendance Record II,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
An attendance record for a student can be represented as a string where each character signifies whether the student was absent
, late
, or present
on that day. The record only contains the following three characters:
- 'A':
Absent
. - 'L':
Late
. - 'P':
Present
.
Any student is eligible for an attendance award if they meet both of the following criteria:
- The student was
absent
('A') for strictly fewer than 2 days total. - The student was never
late
('L') for 3 or more consecutive days.
Given an integer n
, return the number of possible attendance records of length n
that make a student eligible for an attendance award. The answer may be very large, so return it modulo \(10^9 + 7\).
Solution
考虑记忆化搜索,用 \(dfs(i,n,absent, late)\) 表示。
点击查看代码
class Solution { private: int mod=1e9+7; int dp[100002][5][5]; int dfs(int i, int n, int absent, int late){ if(absent>1 || late>=3) return 0; if(i==n) return 1; if(dp[i][absent][late]!=-1) return dp[i][absent][late]; int ans=0; // absent ans = (ans%mod + dfs(i+1, n, absent+1, 0)%mod)%mod; // late ans = (ans%mod + dfs(i+1, n, absent, late+1)%mod)%mod; // pre ans = (ans%mod + dfs(i+1, n, absent, 0)%mod)%mod; return dp[i][absent][late]=ans; } public: int checkRecord(int n) { memset(dp, -1, sizeof(dp)); return dfs(0, n, 0,0); } };
这篇关于[Google] LeetCode 552 Student Attendance Record II的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-01got an unexpected keyword argument
- 2024-03-30维多利亚的秘密 golang入坑系统
- 2024-03-29mongodb sort by date
- 2024-03-29go swagger
- 2024-03-25mongodb cdc
- 2024-03-25how to use go in vscode
- 2024-03-22mongooseserverselectionerror: connect econnrefused ::1:27017
- 2024-03-21pymongo insert_many
- 2024-03-18projection mongodb
- 2024-03-14clickhouse-go