Project Euler 164

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

Q164.
20桁で最初が0でなく、連続する3桁を足していずれも9以下になる自然数の個数

n桁で最後の2桁が決まった連続する3桁を足していずれも9以下になる自然数の個数を求める漸化式を作る。



def calc_g(n, k, l):
if n == 2:
if k == 0 or k + l > M:
return 0
else:
return 1
else:
s = 0
for m in range(10):
if k + l + m <= M:
s += g[n-1][m][k]
return s

N = 20
M = 9
g = [ 0 ] * (N + 1)
for n in range(2, N + 1):
g[n] = [ ]
for k in range(10):
a = [ ]
for l in range(10):
a.append(calc_g(n, k, l))
g[n].append(a)

print sum(map(sum, g[n]))