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...
(source: projecteuler.net)
# 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)]