Projet Euler # 15 "Lattice Path" en Python
Problème 15 "Chemin du treillis"
Si vous partez du coin supérieur gauche du carré 2x2, il y a 6 itinéraires qui vont en bas à droite sans revenir en arrière.
Alors, combien d'itinéraires y a-t-il dans le carré 20 × 20?
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
résultat
137846528820
True
Recommended Posts