# Lattice path from Project Euler with Python solution

I was trying to solve this problem called lattice path from Project Euler:

Count the number of unique paths to travel from the top left to the bottom right of a lattice of squares.

How many such routes are there through a 20×20 grid? It takes me forever to get an answer...

    #  Input:     An interger N (which is the size of the lattice)
#  Output:    An interger (which represents the number of unique paths)
#
#  Example:   input: 2
#
#             (2 x 2 lattice of squares)
#              __ __
#             |__|__|
#             |__|__|
#


When moving through the lattice, you can only move either down or to the right.

I currently have 1 solution, and I am not sure how much better if we memoize it. But I wanted to ask for code review for my solution below:

def lattice_paths(m, n):
if m == 0 and n == 0:
return 1
if m < 0 or n < 0:
return 0
return lattice_paths(m - 1, n) + lattice_paths(m, n - 1)

Here is the time complexity and space complexity of my first solution.
# Time Complexity: O(2^(M+N))
# Auxiliary Space Complexity: O(M+N)


Dynamic approach with the memorized solution:

def lattice_paths(m, n): # m rows and n columns

def helper(x, y):

if x > helper.m or y > helper.n:
return 0
if helper.cache.get((x, y)) is not None:
return helper.cache[(x, y)]

helper.cache[(x, y)] = helper(x + 1, y) + helper(x, y + 1)
return helper.cache[(x, y)]
helper.cache = {}

helper.m = m
helper.n = n
helper(0,0)

if m  ==  0 and n == 0:
return 1
elif m < 0 or n < 0:
return 0
else:
return helper.cache[(0, 0)]

• That's more of a mathematics and algorithm problem than a coding one. Check out this excellent blog post – Daniel Lenz Aug 2 '18 at 21:44

All of your approaches are very brute force. The answer can be computed with a bit of mathematical reasoning. For an m × n lattice, all paths will have m + n segments, of which m segments will go down and n segments will go right. So, out of m + n slots, count the ways to pick m downward moves; the rest of them will be rightward moves. The number of paths is:

$${m + n \choose m} = {m + n \choose n} = \frac{(m+n)!}{m! \, n!}$$

So, the Python solution is simply:

from math import factorial

def lattice_paths(m, n):
return factorial(m + n) // factorial(m) // factorial(n)


Even though the calculation involves large factorials, Python supports big integers seamlessly, and arrives at the answer nearly instantaneously.

here's a solution that uses cache to memoize the solution

def lattice_paths(m, n):
cache = [1]
larger = max(m, n)
smaller = min(m, n)
while(len(cache) < larger + 1):
for i in range(1, len(cache)):
cache[i] += cache[i - 1]
cache.append(2 * cache[len(cache) - 1])
return cache[smaller]

# Time Complexity: O(N)
# Auxiliary Space Complexity: O(N)