Project Euler # 15 "Lattice Path" in Python
If you start from the upper left of the 2 × 2 square, there are 6 routes that go to the lower right without turning back.
Then, how many routes are there in the 20 × 20 square?
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
result
137846528820
True
Recommended Posts