Project Euler 151から（1）

この問題は前回やったようにメモ化を使って簡単に解けますが、動的計画法（DP）ではどうでしょうか。DPの問題点はどの状態になるかどうかわからないところです。よく例に出されるフィボナッチ数列なら、n項をF_nとして、F₁ = F₂ = 1として、F₃から順に求めていけばよいですが、この問題ではどの状態を計算すればよいかが難しいです。与えられた状態が計算が必要な状態かの判定すら難しいです。そこでまず、状態数を求めましょう。
紙の種類の数をNとします。問題のようにA5まであるならN = 5です。前回のPythonのコードを少し改変すれば状態数を数えることができます。

import sys

def next(s, k):
    return s[:k] + (s[k] - 1,) + tuple(n + 1 for n in s[k+1:])

def E(s):
    if s in s_set:
        return
    else:
        s_set.add(s)
    
    num_papers = sum(s)
    if num_papers == 0:
        return
    
    for s1 in (next(s, k) for k in xrange(len(s)) if s[k] > 0):
        E(s1)

N = int(sys.argv[1])
s_set = set()
s0 = (1,) + (0,) * (N - 1)
E(s0)
print len(s_set)

Nに対する状態数は、

2 : 3, 3 : 6, 4 : 18, 5 : 87, 6 : 699, 7 : 9552, 8 : 226593

このように求まります。しかし、これ以上は時間がかかりすぎて難しいようです。なんとか効率的に求められないでしょうか。