# Grid Traveler Recursive Memoization

Updated: 01 February 2024

# Problem

A traveler on a 2D grid begins in the top left and must travel to the bottom right corner by only moving down or right

How many ways can you travel to the goal on a grid that is `m*n`

The resulting travel for a 2x3 grid may look like so:

Some special cases we want to ensure we can handle as well:

```
gridTraveler(1,1) = 1
gridTraveler(m,0) = 0
gridTraveler(0,n) = 0
gridTraveler(m,1) = 1
gridTraveler(1,n) = 0
```

Looking at the example, we can think about how any movement from a point in a grid shrinks the grid in some direction

From this idea we can see that the problem is somewhat recursive, we can visualize this problem as a tree that will look something like this:

Any node that has a `0`

or `1`

can be considered the base case where we know the number of routes that can be travelled. Furthermore, we can also see that there are some repeated nodes

# Base Implementation

`dynamic-programming/memoization/grid-traveler.ts`

```
export const gridTraveler = (m: number, n: number): number => {
if (m == 1 && n == 1) return 1;
if (m == 0 || n == 0) return 0;
return gridTraveler(m - 1, n) + gridTraveler(m, n - 1);
};
```

This implementation starts to look a lot like the Fibonacci Implementation

In the tree for this implementation the time complexity will be $O(2^(m+n))$ and the space complexity is $O(n+m)$

# With memoization

If we look at the tree we see that some subtrees are repeated directly, so we can try to memoize these.

`dynamic-programming/memoization/grid-traveler-memo.ts`

```
const getKey = (m: number, n: number) => `${m},${n}`;
export const gridTraveler = (
m: number,
n: number,
memo: Record<string, number> = {}
): number => {
const key = getKey(m, n);
if (key in memo) return memo[key];
if (m == 1 && n == 1) return 1;
if (m == 0 || n == 0) return 0;
const result = gridTraveler(m - 1, n, memo) + gridTraveler(m, n - 1, memo);
memo[key] = result;
return result;
};
```

Thinking further about it we can consider that the number of solutions of `2,3`

is the same as `3,2`

. We can also consider this for a further optimization but that is not implemented here