# 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