algorithm - 这个脑筋急转弯的易于实现的解决方案？

Question

所以我读了一个脑筋急转弯，内容是关于我们大学的一个算法和谜题聚会，内容如下:

There's a school that awards students that, during a given period, are never late more than once and who don't ever happen to be absent for three or more consecutive days. How many possible permutations with repetitions of presence (or lack thereof) can we build for a given timeframe that grant the student an award? Assume that each day is just a state On-time, Late or Absent for the whole day, don't worry about specific classes. Example: for three day timeframes, we can create 19 such permutations with repetitions that grant an award.

我昨天已经在 math.SE 上发布了它，因为我很感兴趣是否可以推导出一些现成的公式来解决它，但事实证明没有，而且所有的转换都非常复杂。

因此，我要问的是 - 您将如何使用算法解决此类问题？我尝试缩小可能性空间，但过了一段时间，所有可能的重复排列变得太多了，算法开始变得非常复杂，但我相信应该有一些易于实现的方法来解决它，尤其是因为大多数谜题我们在聚会上的交流就像那样。

Answer 1

这是在@ProgrammerPerson 的回答中实现递归的 Python 3 代码的简化版本:

from functools import lru_cache

def count_variants(max_late, base_absent, period_length):
    """
    max_late – maximum allowed number of days the student can be late;
    base_absent – the number of consecutive days the student can be absent;
    period_length – days in a period."""

    @lru_cache(max_late * base_absent * period_length)
    def count(late, absent, days):
        if late < 0: return 0
        if absent < 0: return 0
        if days == 0: return 1
        return (count(late, base_absent, days-1) +   # Student is on time. Absent reset.
                count(late-1, base_absent, days-1) + # Student is late. Absent reset.
                count(late, absent-1, days-1))       # Student is absent.
    return count(max_late, base_absent, period_length)

运行示例:

In [2]: count_variants(1, 2, 3)
Out[2]: 19