题目191：有奖字符串

欧拉计划

Prize Strings

A particular school offers cash rewards to children with good attendance and punctuality. If they are absent for three consecutive days or late on more than one occasion then they forfeit their prize.

During an n-day period a trinary string is formed for each child consisting of L's (late), O's (on time), and A's (absent).

Although there are eighty-one trinary strings for a 4-day period that can be formed, exactly forty-three strings would lead to a prize:



How many "prize" strings exist over a 30-day period?

题目：

某个学校财大气粗，不迟到、不旷课的好学生会得到现金的奖励。但是，如果学生连续三天不上课或迟到不只一次的话，奖励就没了。（迟到比旷课的惩罚还狠……）

如果以 n 天为一个时间段，则可以为每个孩子构造一个字符串，字符串的每个结点可能是下面三种状态之一： L (迟到次数)，O (准时次数)，或者A (旷课次数)

如果把 4 天分成一个时间段，我们可以得到 81 种组合得到的串，其中，有 43 种情况是可以得到奖励的：



那么，如果每 30 天划分成一个时间段，那么，有多少种情况是可以得到奖励的呢？

jerryxjr1220

这题粗看上去还是比较复杂的，一开始我准备穷举所有情况，但是算了一下一共有3**30种可能，然后就放弃了。
换一种思路，可以利用动态规划的思想：
假设没有迟到的情况下，n天获得奖励的情况是F(n)，
那么当第1天为“O”时，f1=F(n-1)
当第1天为“A”,第2天为“O”时，f2=F(n-2)
当第1天为“A”,第2天为“A”，第3天为“O”时，f3=F(n-3)
F(n) = f1+f2+f3 = F(n-1)+F(n-2)+F(n-3), F(0) = 1, F(1) = 2, F(2) = 4
有1天迟到的情况下，把n天看成前i天不迟到+第i天迟到+后n-1-i天不迟到的情况。
F'(n) = sum((F(i)*F(n-1-i) for i in range(n)))
这样只要统计总天数就可以了。
S(n) = F(n) + F'(n)

from functools import lru_cache
@lru_cache(maxsize=None)
def F(n):
        return 2**n if n<3 else F(n-1)+F(n-2)+F(n-3)

def S(n):
        return F(n) + sum((F(i)*F(n-1-i) for i in range(n)))

print(S(30))

1918080160
[Finished in 0.2s]