# Dynamic Programming Part -2: Grid Traveler Memoization

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)`:

![](https://i.postimg.cc/Wb0gPLg3/JPEG-image-4-CC2-AA66-C2-0.jpg align="left")

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](https://harishkunchala.com/dynamic-programming-part-1-basic-memoization#heading-fibonacci-series): `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:

```python
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:

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