监狱逃脱状态计数算法：O(n) 时间复杂度

假设有一个监狱有 N 个房间，每个房间对应一个囚犯，并且有 M 种宗教，每个囚犯都遵循其中一种。如果相邻房间的囚犯属于同一宗教，则可能会发生逃脱。

问题： 给定 N 个房间和 M 种宗教，请编写一个 O(n) 算法来确定可能发生逃脱的总状态数。

例如： 如果有 3 个房间和 2 种宗教，则会有 6 种不同的逃脱状态。

算法思路：

创建数组： 创建一个长度为 N 的数组 states，用来记录每个房间的宗教信仰状态。
初始化计数器： 初始化一个变量 count，用来记录可以发生逃脱的状态数。
遍历数组： 遍历 states 数组，对于每个房间 i：
- 第一个房间： 如果 i 是第一个房间，则 states[i] 的状态数为 M。
- 其他房间： 如果 i 不是第一个房间，则 states[i] 的状态数为 states[i-1] 的状态数乘以 M-1。
- 累加计数： 将 count 累加 states[i] 的状态数。
返回结果： 返回 count 作为最终结果。

伪代码：

function countEscapeStates(N, M):
    states = new Array(N)
    count = 0
    for i from 0 to N-1:
        if i == 0:
            states[i] = M
        else:
            states[i] = states[i-1] * (M-1)
        count += states[i]
    return count

正确性证明：

对于每个房间 i，states[i] 的值表示第 i 个房间的宗教信仰状态数。根据题目要求，如果相邻房间的宗教信仰相同，就可以发生逃脱。因此，对于每个房间 i，只需要考虑其与前一个房间的宗教信仰状态数即可。

如果 i 是第一个房间，则有 M 种宗教信仰状态。
如果 i 不是第一个房间，则有 states[i-1] 种宗教信仰状态，但需要排除与前一个房间相同的宗教信仰状态，即 M-1 种。

因此，states[i] 的状态数为 states[i-1] 乘以 M-1。最终，将所有房间的状态数累加即可得到可以发生逃脱的状态数。

时间复杂度：

该算法的时间复杂度为 O(n)，其中 n 为房间数。算法只需遍历一次房间数组，对于每个房间进行常数时间的操作。因此，时间复杂度为 O(n)。

例子说明：

假设有 3 个房间和 2 种宗教。

房间 1：有 2 种宗教信仰状态。
房间 2：有 1 种宗教信仰状态 (与房间 1 不同的状态)。
房间 3：有 1 种宗教信仰状态 (与房间 2 不同的状态)。

因此，总共有 2 + 1 + 1 = 4 种逃脱状态。

总结：

该算法通过利用递推关系，在 O(n) 时间内有效地计算出了监狱逃脱的总状态数。它直观易懂，并且易于实现。