Hey everyone we are back with another Memoization Problem.

## Grid Problem:

How many can a person travel from the top left corner of the grid to the bottom right corner. The only restriction is that we can only move down or right.l

### General Grid Travel:

Let's look at an example of the following grid:

`gridTraveler(2,3)`

-> 3.

a(1,1)

**to**a(1,2)**to**a(1,3)**to**a(2,3)a(1,1)

**to**a(2,1)**to**a(2,2)**to**a(2,3)a(1,1)

**to**a(1,2)**to**a(2,2)**to**a(2,3)

### Basic Case:

Let's take the basic case

`gridTraveler(1,1)`

-> 1.

Here since it's just a Grid with One column and One Row. We don't have to do anything.

Now we have some illogical cases, where there is no answer such as:

`gridTraveler(1,0)`

-> 0 . We cannot do anything if there are no columns`gridTraveler(0,1)`

-> 0. We cannot do anything if there are no rows

So for all the illogical cases, we'll return 0.

#### Node Diagram:

If we look at the node diagram for `gridTraveler(2,3)`

:

We can see that it basically a fibonacci. Where we are adding the values of the children to the parent.

**Time complexity** = O(2 ^(m + n))

**Space complexity** = O(m + n)

So we can write: `gridTraveler(2,3)`

= `gridTraveler(1,3)`

+ `gridTraveler(2,2)`

This is similar to our fibonacci: `fib(n)`

= `fib(n-1)`

+ `fib(n-2)`

So we can apply a similar algorithm here using memoization.

### Recursion Algorithm:

Here's the Recursion algorithm:

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

And as we said before :

**Time complexity** = O(2 ^(m + n))

**Space complexity** = O(m + n)

### Memoized Algorithm

And here's the memoized algorithm:

```
def grid_traveler(m, n, memo={}):
if (m, n) in memo:
return memo[(m, n)]
if m == 1 and n == 1:
return 1
if m == 0 or n == 0:
return 0
memo[(m, n)] = grid_traveler(m - 1, n, memo) + grid_traveler(m, n
- 1, memo)
return memo[(m, n)]
```

**New Time Complexity** = O(m * n)

**New Space Complexity** = O(m + n)

Since memoization is one of the fundamental blocks of dynamic programming. Make sure to practice lots of problems in it as a lot of interviews generally ask this.