How to improve (speed, memory usage) search for unique number of paths to reach opposite corner algorithm?

Question

I have m x n grid. m >= 1 ; n >= 1

I have item in the top-left corner and need to reach bottom-right corner of the grid.

Item can only move either down or right.

I need to find possible unique paths to do it.

I made two solutions for the problem: recursion (slower than the below one) and the one below.

The problem is that I run out of memory when m and n are big e.g. m == 20 and n >= 15 (more than 4 Gb is used - all free memory I have).

How can I improve my solution or there should be absolutely other way to solve the problem?

def unique_paths(m, n):
    assert isinstance(m, int), "m should be integer"
    assert isinstance(n, int), "n shoudl be integer"
    assert m >= 1, "m should be >= 1"
    assert n >= 1, "n should be >= 1"
    if m == 1 and n == 1:  # border case
        return 1

    ch = [(m, n,)]  # for first start
    s = 0  # number of unique paths
    while True:
        new_ch = []
        while ch:
            i = ch.pop()  # I assumed that if decrease len of list it would decrease memory use
            if i[0] == 1 and i[1] == 1:  # we reached opposite corner
                s += 1

            # all other cases:

            elif i[0] != 1 and i[1] != 1:
                new_ch.append((i[0], i[1] - 1, ))
                new_ch.append((i[0] - 1, i[1]))

            elif i[0] == 1 and i[1] != 1:
                new_ch.append((i[0], i[1] - 1,))

            else:
                new_ch.append((i[0] - 1, i[1],))

            del i  # do not need i anymore

        if not new_ch:
            return s
        del ch
        ch = new_ch
        del new_ch

if __name__ == '__main__':
    print(unique_paths(7, 3))  # = 28 - test case

EDIT:

Solution: recursion with memoization works really well! Many thanks to Zabir Al Nazi.

With the help of python lru_cache decorator:

@lru_cache(128)
def number_of_paths(m, n):
    if m == 1 and n == 1:  # border case
        result = 1

    elif m != 1 and n != 1:
        result = number_of_paths(m - 1, n) + number_of_paths(m, n - 1)

    elif m != 1 and n == 1:
        result = number_of_paths(m - 1, n)

    elif m == 1 and n != 1:
        result = number_of_paths(m, n - 1)

    else:
        raise Exception("Something went wrong!")

    return result

With the help of dictionary to store results:

storage = {}
def number_of_paths_no_lru(m, n):
    if storage.get((m, n,)):
        return storage[(m, n)]

    if m == 1 and n == 1:  # border case
        result = 1

    elif m != 1 and n != 1:
        result = number_of_paths_no_lru(m - 1, n) + number_of_paths_no_lru(m, n - 1)

    elif m != 1 and n == 1:
        result = number_of_paths_no_lru(m - 1, n)

    elif m == 1 and n != 1:
        result = number_of_paths_no_lru(m, n - 1)

    else:
        raise Exception("Something went wrong!")

    storage[(m, n, )] = result
    return result

Tests:

if __name__ == '__main__':
    print(number_of_paths(100, 100))
    print(number_of_paths_no_lru(100, 100))
    # Answers:
    # 22750883079422934966181954039568885395604168260154104734000
    # 22750883079422934966181954039568885395604168260154104734000

Answer 1

The problem with your approach is you're taking the same steps repeatedly. It's the first brute-force approach that someone should try.

For starter, you can try to increase the recursion limit for python.

import sys
sys.setrecursionlimit(1500)

But it will fail if you start increasing m, or n. As the complexity grows exponentially.

One way to improve is to break the problem down into smaller parts and solve for the smaller parts and merge them into the final solution.

Think, you are in the green position and want to go to the blue one. That's the main solution. But, let's imagine the smaller sub-grid with red boundary, the red grid has a starting point at the orange marker and endpoint at blue, now let's say in some magical way we know the solution for the red sub-grid, can't we just merge the solution for going from green to orange + red grid part?

Now, this recursive idea can be implemented in the following way.

def numberOfPaths(m, n): 
    if(m == 1 or n == 1): 
        return 1

    return numberOfPaths(m-1, n) + numberOfPaths(m, n-1)  # traversal in the two possible directions

m = 20
n = 20
print(numberOfPaths(m, n)) 

But the complexity is still exponential, as the program tries all possible combinations for finding a solution over and over again. What if we use a map to save all the partial solutions? We can save the solution for red sub-grid and just use it from our map without re-traversing it again?

This concept is called dynamic programming and it's very well known. So, I won't go to any details.

We can create a 2-d array answers[m][n] it will be initialized with -1; if we know the solution from a sub-grid m_1, n_1 we just return the answer instead of traversing.

This brings down the complexity to O(mxn).

import numpy as np

global answers

def numberOfPaths(m, n): 
    if(m == 1 or n == 1): 
        return 1
    global answers
    if answers[m][n] != -1:
        return answers[m][n]


    answers[m][n] = numberOfPaths(m-1, n) + numberOfPaths(m, n-1)  # traversal

    return answers[m][n]

m = 6
n = 6

answers = np.ones((m+1,n+1))*-1

print(numberOfPaths(m, n)) 

It's already a major improvement.

We can completely re-invent the problem as a combinatorial one too.

Look, there are m rows, n columns, if you start from top-left, you can take any set of moves (right or down), but your initial cell and final cell are fixed. So, how many possible options do you have to make moves? (m+n-2) (initial and final cell fixed so -2) Now, from all these possible moves you can only select n-1 if we consider the columns, or m-1 if we consider the rows. So, the solution will be (m+n-2)C(n-1) or (m+n-2)C(m-1).

Now, for smaller integers where m! or n! don't overflow (luckily python integers can handle large values easily), this can be done in linear time O(max(m,n)). As nCr can be calculated in terms of factorials only.