无妄，往吉

0%

Finite-State Machine

发表于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

有限状态机（Finite-State Machine, FSM）表示有限个状态以及在这些状态之间的转移和动作等行为的数学计算模型。状态机可归纳为4个要素，即现态、条件、动作、次态。“现态”和“条件”是因，“动作”和“次态”是果。

详解如下：

① 现态：是指当前所处的状态。

② 条件：又称为“事件”。当一个条件被满足，将会触发一个动作，或者执行一次状态的迁移。

③ 动作：条件满足后执行的动作。动作执行完毕后，可以迁移到新的状态，也可以仍旧保持原状态。动作不是必需的，当条件满足后，也可以不执行任何动作，直接迁移到新状态。

④ 次态：条件满足后要迁往的新状态。“次态”是相对于“现态”而言的，“次态”一旦被激活，就转变成新的“现态”了。

有限状态机对于算法求解具有重要的意义，其可以简化问题，使得复杂的递推关系转换为简单的状态转移问题。比如：

552. 学生出勤记录 II

给定一个正整数n，返回长度为n的所有可被视为可奖励的出勤记录的数量。 答案可能非常大，你只需返回结果mod 1e9 + 7的值。

学生出勤记录是只包含以下三个字符的字符串：

  1. ‘A’ : Absent，缺勤
  2. ‘L’ : Late，迟到
  3. ‘P’ : Present，到场
    如果记录不包含多于一个’A’（缺勤）或超过两个连续的’L’（迟到），则该记录被视为可奖励的。
Simple test cases
1
2
3
4
5
6
输入: n = 2
输出: 8 
解释：
有8个长度为2的记录将被视为可奖励：
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
只有"AA"不会被视为可奖励，因为缺勤次数超过一次。

对于这个问题，我们的直觉是通过构造全排列，并依照判断条件，对符合条件的记录进行计数。显然，依照直觉暴力求解，必然会遇到超时问题。更好的思路是基于动态规划的思想，构造状态转移方程。但就本题而言，借助有限状态机，会大大地简化问题。

先来看题目，对于不可奖励的记录，其要么包含2+的A，或3+的连续的L，那么，仅仅需要考虑A和L的情况，我们将有限状态机画出来，得到：
有限状态机

由上图可见，对于节点A0L0，其入度为3，而节点A1L0入度为6，那么代码可以表示为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int checkRecord(int n) {
        int m = 1e9 + 7;
        
        long long a0l0 = 1, a0l1 = 0, a0l2 = 0, a1l0 = 0, a1l1 = 0, a1l2 = 0;
        for (int i = 0; i <= n; ++i) {
            long long a0l0_ = (a0l0 + a0l1 + a0l2) % m;
            a0l2 = a0l1;
            a0l1 = a0l0;
            a0l0 = a0l0_;
            long long a1l0_ = (a0l0 + a1l0 + a1l1 + a1l2) % m;
            a1l2 = a1l1;
            a1l1 = a1l0;
            a1l0 = a1l0_;
        }

        return (int)a1l0;
    }
};

以上！