trjhtr

I was trying to solve this problem called lattice path from Project Euler that "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...

Image https://projecteuler.net/project/images/p015.gif

 # 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.

Currently, I got 1 solution, and I am not sure how much better if we memoize it. But 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)]

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)