プロジェクトオイラー 問１１４

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問１１４「ブロックの組み合わせ方の数え上げ その1」
長さ 7 ユニットからなる 1 列上に, 最低 3 ユニットの長さを持つ赤ブロックが置かれている. 
ただしどの赤ブロック同士も, 少なくとも 1 ユニットの黒い正方形が間にある(赤ブロックは長さが異なってもよい). 
これを敷き詰める方法は, ちょうど 17 通りある.

50 ユニットの長さの 1 列を敷き詰める方法は何通りあるか.

注意: 上の例では起こりえないが, 通常はブロックの大きさが複数混ざっていてもよい. 
例えば, 8 ユニットの長さの 1 列では, 赤(3), 黒(1), 赤(4) を使うことができる.







注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の回答例は以下の通りです。

def endb(n, bd, rd):
	if n not in bd:
		bd[n] = endb(n-1, bd, rd) + endr(n-1, bd, rd)
	return bd[n]

def endr(n, bd, rd):
	if n not in rd:
		rd[n] = 1 + sum([endb(i,bd,rd) for i in xrange(n-2)])
	return rd[n]

def f(n):
	bd, rd = {0:0, 1:1}, {0:0, 1:0, 2:0, 3:1}
	return endb(n, bd, rd) + endr(n, bd, rd)

n=50
s = f(n)
print s

黒ブロック（長さ１個）または赤ブロック（長さ３個以上）を１つずつ置いていって個数を数えます。
ただし、赤ブロックは連続では置けないので、
順番に並べていく中で終端が赤か黒かで別々の関数にします。

１．関数endb(n, bd, rd)
・全体がn個で終端が黒ブロックのパターン数を返します。
・bdは終端が黒で全体がn個の場合のパターン数の辞書（連想配列）です。
　rdは終端が赤で全体がn個の場合のパターン数の辞書（連想配列）です。
　いずれも1度計算した値はこれらの辞書に格納して重複して計算しないようにします。
・終端に黒ブロックを置いて全体がn個になる場合、
　全体がn-1個で終端が赤でも黒でも置けるので、これらのパターン数の和になります。

２．関数endr(n, bd, rd)
・全体がn個で終端が黒ブロックのパターン数を返します。
・bd、rdは関数endbのときと同様です。
・終端に赤ブロックを置いて全体がn個になる場合は以下の２つの場合があります。
　a.まだ何も置いていなくて長さn個の赤ブロックを置く場合
　b.端が黒でn個まで2個以上のすきまがあり、すきまの長さ+1個の赤ブロックを置く場合
　　この場合、置く直前のブロックは黒ブロックの場合だけなのでendb関数を呼び出します。

　aの場合は1パターンなので赤辞書rdのキーnの初期値に1として設定します。
　bの場合はループ変数iを0からnの3つ手前まで回して、長さiの黒ブロックで終わって長さn-iの赤ブロックを1つ置くパターン数を足します。

３．関数f(n)
・問題の条件で長さnで1列を敷き詰めるパターン数を返します。
・bd、rdは関数endbのときと同様です。
　最小の長さは黒が1個で赤が3個なので、黒赤それぞれでこの値未満のパターン数は0で、その値で1パターンというのが初期値になります。
・黒赤それぞれのが終端となるパターン数の和が、求めるパターン数です。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
16475640049