Projekt Euler # 15 "Gitterpfad" in Python
Wenn Sie oben links auf dem 2x2-Quadrat beginnen, gibt es 6 Routen, die rechts unten verlaufen, ohne umzukehren.
Wie viele Routen gibt es dann auf dem 20 × 20-Quadrat?
Python
# n = 2
n = 20
route_nums = {}
seq = range(1, n+2)
def compute_route_num(i, j):
if(i == 1 or j == 1):
return 1
else:
return route_nums[(i-1, j)] + route_nums[(i, j-1)]
for i in seq:
for j in seq:
route = compute_route_num(i, j)
route_nums[(i, j)] = route
result = route_nums[(n+1, n+1)]
result
print result
print result == 137846528820
Ergebnis
137846528820
True
Recommended Posts