プロジェクトオイラー
http://projecteuler.net/index.php
Q114.
長さnの列を色々な長さのブロックで埋める。ただし、長さ2は不可、また2より長いブロックは並んではいけない。n=50のときのブロックの埋め方は何通りあるか。
長さnの埋め方をan、一番左のブロックの長さが1であるときの埋め方をbnとする。一番左のブロックで場合わけすると漸化式が作れる。
a0 = 1
a1 = a0
a2 = a1 + 1
a3 = a2 + 1
a4 = a3 + b1 + 1
an = an-1 + bn-3 + ... + b1 + 1
bn = an-1
より、
an = an-1 + an-4 + ... + a0 + 1
となる。
ここから117までほとんど同じ。
N = 50
a = [ 1, 1, 1 ]for n in range(3, N + 1):
s = a[n-1] + 1
for i in range(n - 3):
s += a[i]
a.append(s)
print a[N]
