Find number of unique paths to reach opposite grid corner

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:

lru_cache is really amazing:

from functools import lru_cache


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

    if m != 1 and n != 1:
        return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1)

    if m != 1 and n == 1:
        return numberOfPaths(m - 1, n)

    if m == 1 and n != 1:
        return numberOfPaths(m, n - 1)


if __name__ == '__main__':
    print(numberOfPaths(100, 100))  # 22750883079422934966181954039568885395604168260154104734000

```

Answer 1

Solution: recursion with memoization works really well! Many thanks to Samwise and vnp.

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