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

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.