Project Euler 114

http://projecteuler.net/index.php?section=problems&id=114

この手の問題は、再帰で書いてメモ化ですね。

def num_ways(n):
    if n <= 2:
        return 1
    else:
        if memo[n] != 0:
            return memo[n]
        
        m = 1 + sum(num_ways(k) for k in range(n - 3) + [ n - 1 ])
        memo[n] = m
        return m

N = 50
memo = [ 0 ] * (N + 1)
print num_ways(N)

漸化式で書くと、

a₀ = 1, a₁ = 1, a₂ = 1
a_n = 1 + a₀ + … a_n-4 + a_n-1

なので、これをコード化したほうが短いですね。

N = 50
a = [ 1 ] * 3
for n in range(3, N + 1):
    a.append(1 + sum(a[k] for k in range(n - 3) + [ n - 1 ]))
print a[N]