学生出勤记录 IIJava

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：

'A'：Absent，缺勤
'L'：Late，迟到
'P'：Present，到场

如果学生能够同时满足下面两个条件，则可以获得出勤奖励：

按总出勤计，学生缺勤（'A'）严格少于两天。
学生不会存在连续 3 天或连续 3 天以上的迟到（'L'）记录。

给你一个整数 n ，表示出勤记录的长度（次数）。请你返回记录长度为 n 时，可能获得出勤奖励的记录情况数量。答案可能很大，所以返回对 109 + 7 取余的结果。

示例 1：

输入：n = 2
输出：8
解释：
有 8 种长度为 2 的记录将被视为可奖励：
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL" 
只有"AA"不会被视为可奖励，因为缺勤次数为 2 次（需要少于 2 次）。

示例 2：

输入：n = 1
输出：3

示例 3：

输入：n = 10101
输出：183236316

提示：

1 <= n <= 10⁵

# 思路

//     分两种情况：
// 1.没有A：即长度为n的字符串，P、L两个字母满足规则的排列数量；
// 2.有一个A：即A将长度为n的字符串分隔为2段，A前面的长度为i，A后面的长度为n-1-i，这两段的情况与情况1相同，只是长度不同，这种情况的排列数量是两段排列数量的乘积，当然，i要从0遍历到n。

// 定义dp数组dp[i][j]，表示第i天，字符串结尾L字符连续的个数为j时，可以获得出勤奖励的记录情况的数量，j取值0，1，2是有意义的，边界条件dp[0][0] = 1。
// dp[i][0]可以由dp[i-1][0]、dp[i-1][1]、dp[i-1][2]转移而来，因为只要今天是P就可以；
// dp[i][1]一定由dp[i-1][0]转移而来，因为今天是L的情况下，昨天只能是P；
// dp[i][2]一定由dp[i-1][1]转移而来，因为两天都是L的情况下，昨天只能是L；

// p.s. 实在不会取模，就用long糊弄了

# 解法


class Solution {
//     分两种情况：
// 1.没有A：即长度为n的字符串，P、L两个字母满足规则的排列数量；
// 2.有一个A：即A将长度为n的字符串分隔为2段，A前面的长度为i，A后面的长度为n-1-i，这两段的情况与情况1相同，只是长度不同，这种情况的排列数量是两段排列数量的乘积，当然，i要从0遍历到n。

// 定义dp数组dp[i][j]，表示第i天，字符串结尾L字符连续的个数为j时，可以获得出勤奖励的记录情况的数量，j取值0，1，2是有意义的，边界条件dp[0][0] = 1。
// dp[i][0]可以由dp[i-1][0]、dp[i-1][1]、dp[i-1][2]转移而来，因为只要今天是P就可以；
// dp[i][1]一定由dp[i-1][0]转移而来，因为今天是L的情况下，昨天只能是P；
// dp[i][2]一定由dp[i-1][1]转移而来，因为两天都是L的情况下，昨天只能是L；

// p.s. 实在不会取模，就用long糊弄了


    private static final int MOD = 1000000007;
    public int checkRecord(int n) {
        long[][] dp = new long[n+1][3];
        dp[0][0] = 1;
        for(int i = 1; i <= n; i++) {
            dp[i][0] = sum(dp, i-1);
            dp[i][1] = dp[i-1][0];
            dp[i][2] = dp[i-1][1];
        }

        long sum1 = sum(dp, n);
        long sum2 = 0;
        for(int i = 0; i < n; i++) {
            sum2 += ((sum(dp, i) * sum(dp, n-1-i)) % MOD);
        }

        return (int) ((sum1 + sum2) % MOD);
    }

    private long sum(long[][] dp, int i) {
        return (((dp[i][0] + dp[i][1]) % MOD) + dp[i][2]) % MOD;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# 总结

分析出几种情况，然后分别对各个情况实现