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

[![https://projecteuler.net/project/images/p015.gif](https://i.stack.imgur.com/dw8Pc.gif)](https://i.stack.imgur.com/dw8Pc.gif)  

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

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)]

```