首页 > 其他分享 >[Google] LeetCode 552 Student Attendance Record II

[Google] LeetCode 552 Student Attendance Record II

时间:2022-09-01 05:22:06浏览次数:57  
标签:absent Google return int dfs 552 II late mod

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);
    }
};

标签:absent,Google,return,int,dfs,552,II,late,mod
From: https://www.cnblogs.com/xinyu04/p/16645147.html

相关文章

  • [Google] LeetCode 489 Robot Room Cleaner
    Youarecontrollingarobotthatislocatedsomewhereinaroom.Theroomismodeledasanmxnbinarygridwhere0representsawalland1representsanempt......
  • 算法 - 螺旋矩阵 II
    59.螺旋矩阵II这道题困扰了我很久,一些边界值控制比较繁琐,但是偶然发现按照以下方法写,在Leetcode可以AC。classSolution{publicstaticint[][]generateMatrix(......
  • Google Chrome谷歌浏览器离完整离线安装包下载地址整理总汇
    每次重装系统,都要为安装Chrome而烦恼。虽然现在可以直接从谷歌浏览器官网下载在线安装包进行安装,但是在线安装包安装的版本不可控,大概率是x86版本,而且在断网状态下也......
  • SP1557 GSS2 - Can you answer these queries II
    SP1557GSS2-CanyouanswerthesequeriesII题目大意给出\(n\)个数,\(q\)次询问,求最大子段和,相同的数只算一次。分析看到一个区间内相同的数只能算一次,经验告诉......
  • 768. 最多能完成排序的块 II
    题目(链接)arr是一个可能包含重复元素的整数数组,我们将这个数组分割成几个“块”,并将这些块分别进行排序。之后再连接起来,使得连接的结果和按升序排序后的原数组相同。我们......
  • 260. 只出现一次的数字 III
     难度中等645收藏分享切换为英文接收动态反馈给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。找出只出现一次的那两个元素。你可以......
  • [Google] LeetCode 715 Range Module 线段树
    ARangeModuleisamodulethattracksrangesofnumbers.Designadatastructuretotracktherangesrepresentedashalf-openintervalsandqueryaboutthem.......
  • FTP的传输有两种方式:ASCII传输模式和二进制数据传输模式
    FTP的传输有两种方式:ASCII传输模式和二进制数据传输模式_boker的博客-CSDN博客_ftp传输二进制 https://blog.csdn.net/z507263441/article/details/38586769FTP的传输有......
  • leetcode-998. 最大二叉树 II
    998.最大二叉树II图床:blogimg/刷题记录/leetcode/998/刷题代码汇总:https://www.cnblogs.com/geaming/p/16428234.html题目思路看到树就要想到递归。解法/***D......
  • 654.最大二叉树+998.最大二叉树II
    654.最大二叉树题目描述给定一个不重复的整数数组 nums。 最大二叉树 可以用下面的算法从 nums递归地构建:创建一个根节点,其值为 nums中的 最大值 。递......