Project Euler 191

プロジェクトオイラー
http://projecteuler.net/index.php

Q191.
3日続けて休むか、遅刻が2回あったら賞がもらえない。30日間で賞がもらえるパターンはいくつあるか。

n日間で今欠席が何回続いていて何回遅刻しているという状態で何通りあるかという数列に対して簡単に漸化式が書ける。

def add(dic, k, v):

    if k in dic:

        dic[k] += v

    else:

        dic[k] = v
N = 30

P = [ { (0, 0): 1 } ]

for k in range(1, N + 1):

    dic = { }

    for s, n in P[k-1].iteritems():

        s1 = (0, s[1])      # O

        add(dic, s1, n)

        if s[1] == 0:       # L

            s1 = (0, 1)

            add(dic, s1, n)

        if s[0] < 2:        # A

            s1 = (s[0] + 1, s[1])

            add(dic, s1, n)

    P.append(dic)

print sum(P[N].itervalues())