跳到主要内容

552. Student Attendance

Student Attendance Record II​

非常适合拿来练习 Bottom Up风格版的DP 题目

这题考的其实是 如何按规定合法『接龙🐲』

规则要先读熟啊​

每个学生每天出勤只有三种情况：

"A"代表Absent缺席、"L"代表Late迟到、"P"代表Present准点

接下来是关键细节 学生想拿出勤奖 必须同时做到 俩个条件：

  1. "A"的次数 严格小于 2
  2. 不能连续 3天得到"L"

因此题目问我们的是 给定一个表示出勤记录长度的正整数nn

问有多少种的出勤记录组合能让学生领取出勤奖

规则明示的大方向​

I. "A"的次数 严格小于 2 说明"A"只能出现0或1次

计数逻辑由此要先拆成『是否曾有"A"』来讨论

因为只要出现过一次"A" 哪怕接下来全"P" 这"A"也不会被抹除

有点像男人一旦外遇了 会给对象留下一辈子的疙瘩这种道理

II. 不能连续 3天得到"L" 这道约束

言下之意就是 我们某天的出勤能否"L"

得看前两天有没有背靠背"L"了

没背靠背的话 才能来个"L"划水一下

猜出DP的状态转移了齁🍷​

1. 未曾有过"A"的状态转移​

这个最好理解啰 有过"A"的所有组合

都没法转移给未曾有过"A"的组合

这是由于我们前面说 一旦缺席过

"A"就永远黏在出勤表上 抹都抹不掉

因此未曾有"A"的状态转移是：

一、长度ii，未曾有过"A"，且结尾是"P"的的合规出勤组合数

来自长度i−1i - 1，未曾"A"的合规出勤组合数加总

(0)CiP=(0)Ci−1P+(0)Ci−1L+(0)Ci−1LL{}^{(0)} C_i^\text{P} = {}^{(0)} C_{i - 1}^\text{P} + {}^{(0)} C_{i - 1}^\text{L} + {}^{(0)} C_{i - 1}^\text{LL}

(0){}^{(0)}代表未曾有过"A"

索引上方的P、L、LL代表出勤序列的尾部情况

索引下方则是指第ii天的出勤情况

毕竟只要没发生过"A" 上一天全部的"P"、"L"、"LL"结尾之合法组合

都能靠著本天的"P"转移过来

澄清一下 "L"和"LL"是不一样的

"L"代表前一天是"L" 但再往前一天不是"L"

"LL"才是指往前两天都是"L"

二、长度ii，未曾有过"A"，且结尾是"L"的的合规出勤组合数

来自长度i−1i - 1，未曾有过"A"，结尾是"P"的合规出勤组合数

(0)CiL=(0)Ci−1P{}^{(0)} C_i^\text{L} = {}^{(0)} C_{i - 1}^\text{P}

可想而知 如果前一天是"L" 那么本天再来个"L"了

就成了 "LL" 尾 而非"L"尾

三、长度ii，未曾有过"A"，且结尾是"LL"的的合规出勤组合数

来自长度i−1i - 1，未曾有过"A"，结尾是"L"的合规出勤组合数

(0)CiLL=(0)Ci−1L{}^{(0)} C_i^\text{LL} = {}^{(0)} C_{i - 1}^\text{L}

本天结束时看见的"LL"尾

肯定是今天"L"然后上一天又"L"

2. 曾有过"A"的状态转移​

比较要注意的来啦 曾有过"A"的状态转移

是能接收到未曾有过"A"的状态转移的

于是接下来四项状态转移 要小心处理：

四、长度ii，曾有过"A"，且结尾是"P"的的合规出勤组合数

来自长度i−1i - 1，曾有过"A"的合规出勤组合数加总

(1)CiP=(1)Ci−1P+(1)Ci−1L+(1)Ci−1LL+(1)Ci−1A{}^{(1)} C_i^\text{P} = {}^{(1)} C_{i - 1}^\text{P} + {}^{(1)} C_{i - 1}^\text{L} + {}^{(1)} C_{i - 1}^\text{LL} + {}^{(1)} C_{i - 1}^\text{A}

(1){}^{(1)}代表曾有过一个"A"

这条公式不难解读 就是前一天当下

看见的所有曾有过"A"的合法组合数 在本天拿了个"P" 转移过来

五、长度ii，曾有过"A"，且结尾是"L"的的合规出勤组合数

来自长度i−1i - 1，曾有过"A"，结尾是"P"或者"A"的合规出勤组合数

(1)CiL=(1)Ci−1P+(1)Ci−1A{}^{(1)} C_i^\text{L} = {}^{(1)} C_{i - 1}^\text{P} + {}^{(1)} C_{i - 1}^\text{A}

前一天结尾"P"或"A" 今天迟到了的转移

六、长度ii，曾有过"A"，且结尾是"LL"的的合规出勤组合数

来自长度i−1i - 1，曾有过"A"，结尾是"L"的合规出勤组合数

(1)CiLL=(1)Ci−1L{}^{(1)} C_i^\text{LL} = {}^{(1)} C_{i - 1}^\text{L}

前一天结尾"L" 今天『又』迟到了的转移

七、长度为ii，曾有过"A"，且结尾是"A"的的合规出勤组合数

这不就是说 本来都没"A" 碰巧今天破功"A"了嘛😏

由此可见状态转移来自那些

长度i−1i - 1，未曾"A"的合规出勤组合数加总

(1)CiA=(0)Ci−1P+(0)Ci−1L+(0)Ci−1LL{}^{(1)} C_i^\text{A} = {}^{(0)} C_{i - 1}^\text{P} + {}^{(0)} C_{i - 1}^\text{L} + {}^{(0)} C_{i - 1}^\text{LL}

3. Base Case在那儿呢​

想当然就是 仅有一天需要统计出勤的案例

因此Base Case仅三种可能结尾："A"、"L"、"P"

也就是(0)C1P=(0)C1L=1,(0)C1LL=0{}^{(0)} C_1^\text{P} = {}^{(0)} C_1^\text{L} = 1, {}^{(0)} C_1^\text{LL} = 0

(1)C1P=(1)C1L=(1)C1LL=0,(1)C1A=1{}^{(1)} C_1^\text{P} = {}^{(1)} C_1^\text{L} = {}^{(1)} C_1^\text{LL} = 0, {}^{(1)} C_1^\text{A} = 1

4. 小小观察​

七道状态转移方程写出来后 心细的各位发现：

I. 上一天结束时 全部未曾有过"A"的合法组合数

可能在今天"A"了 走第七道：全部转移到曾有过"A"且结尾就是"A"的状态

亦有可能今天"P" 走第一道：继续留守全部未曾有过"A"的合法组合数

II. 第三道和第六道是非常雷同的状态转移方程

区别仅在左方象徵有无"A"过的索引

III. 第二道和第五道也是相当相似的

不同的点在于 第五道需要考虑上一天结尾是"A"的合法组合数

IV. 第四道和第一道叫做『内部全额转移』

白话文讲就是 只要你今天"P" 那么你能继承的上一天状态就包括

与你同样数量的"A"的所有合法组合数

『与你同样数量的"A"』正是『内部』的意思

如果能Bottom Up做到O(1)O(1)空间​

那就没需要还写递归cache 搞到O(n)O(n)空间复杂度

其实不用如此cache的 纯Bottom Up亦是O(n)O(n)时间复杂度

#include <cmath>
#include <vector>
using namespace std;

int countPossibilities(int recordLen) // LeetCode Q.552.
{
    // Possible ends: "P", "L", "LL".
    long long noAbsEndP = 1, noAbsEndL = 1, noAbsEndLL = 0;

    // Possible ends: "P", "L", "LL", "A".
    long long oneAbsEndP = 0, oneAbsEndL = 0, oneAbsEndLL = 0, oneAbsEndA = 1;

    // Helper variables: help each day's branch counts update values.
    long long newNoAbsEndP = 0, newNoAbsEndL = 0, newNoAbsEndLL = 0;

    long long newOneAbsEndP = 0, newOneAbsEndL = 0, newOneAbsEndLL = 0, newOneAbsEndA = 0;

    long long modulo = pow(10, 9) + 7; // Long long prevents overflow.

    for (int day = 2; day <= recordLen; day++) {
        long long noAbsSum = noAbsEndP + noAbsEndL + noAbsEndLL;
        noAbsSum %= modulo;

        newNoAbsEndP = noAbsSum % modulo; // No.1: all 0 absence ends are now "P".

        newNoAbsEndL = noAbsEndP; // No.2: 0 absence end "P" => "L".
        newNoAbsEndLL = noAbsEndL; // No.3: 0 absence end "L" => "LL".

        long long oneAbsSum = oneAbsEndP + oneAbsEndL + oneAbsEndLL + oneAbsEndA;
        oneAbsSum %= modulo;

        newOneAbsEndP = oneAbsSum % modulo; // No.4: all 1 absence ends are now "P".

        // No.5: 1 absence end from "P" or "A" to "L".
        newOneAbsEndL = (oneAbsEndP + oneAbsEndA) % modulo;

        newOneAbsEndLL = oneAbsEndL; // No.6: 1 absence end "l" => "ll".

        newOneAbsEndA = noAbsSum % modulo; // No.7: from 0 to 1 absence.

        // Transit updated counts.
        noAbsEndP = newNoAbsEndP, noAbsEndL = newNoAbsEndL, noAbsEndLL = newNoAbsEndLL;

        oneAbsEndP = newOneAbsEndP, oneAbsEndL = newOneAbsEndL;
        oneAbsEndLL = newOneAbsEndLL, oneAbsEndA = newOneAbsEndA;

        // Reset helper variables for next day's usage.
        newNoAbsEndP = 0, newNoAbsEndL = 0, newNoAbsEndLL = 0;

        newOneAbsEndP = 0, newOneAbsEndL = 0, newOneAbsEndLL = 0, newOneAbsEndA = 0;
    }

    long long validCounts = (noAbsEndP + noAbsEndL + noAbsEndLL) % modulo;

    validCounts += (oneAbsEndP + oneAbsEndL + oneAbsEndLL + oneAbsEndA) % modulo;

    return validCounts % modulo;
}

因为这题无需绝对值 我就把abs当做absence缩写

然后要时不时Modulo控制大小 避免天文数字炸裂

然后我的recordLen/record_len变量名

其实就是LeetCode官网上的n参数

Bottom Up Efficiency Bottom Up搞定一切～～

延伸问题​

I. 从常理想 第二天结束的时候

肯定不会有出勤记录是尾部"LL"且还缺席过一次的

然而第六道状态转移方程的代码长这样

new_one_abs_table["ll"] = one_abs_table["l"] # No.6: 1 absence end "l" => "ll".

为什么这边不用先加上是否正在第二天的if判别 依然能有正确性呢😌

II. "LLL"被判定为没资格领出勤奖

但是更糟的"LLA"竟然还没出局 题目设计骚操作🤡

问题来了：如果要让"LLA"自动出局

那么我们该怎么修改状态转移方程呢