Есть ли более эффективный способ расчета смещения для всех возможных путей в сетке?

Question

Я пытаюсь написать алгоритм на Python, который может рассчитать и сохранить максимальное смещение для всех возможных путей в сетке n на m.Там нет никаких препятствий.Мы начинаем с начала координат и можем каждый раз двигаться вверх или вправо на одну единицу длины сетки.Для каждого пути я вычисляю максимальное смещение (используя предопределенную формулу), и это смещение затем добавляется в список, чтобы к нему можно было получить доступ после завершения программы.

Я могу рассчитать максимальное смещение для каждого пути безпроблема, и я реализовал свое решение так, что сохраняется только результат расчета, так как без этого ОЗУ перегружалось.Похоже, что он отлично работает с размером сетки 10 на 10. Однако, когда я рассматриваю сетку большего размера, например 30 на 30, расчет займет трудоемкое время, поскольку существует огромное количество путей для создания.Код, который я использую, приведен ниже.

# This function creates the initial path list and calls the function
# to create all possible paths
def findPaths(startRow,startCol,endRow,endCol): 
    path = [0 for d in range(endRow+endCol-startRow-startCol-1)] 
    findPathsUtil(endRow,endCol,startRow,startCol,path,0)

# This function is called iteratively until either of the if conditions are met
def findPathsUtil(endRow,endCol,currRow,currCol,path,indx):
    global count_global

    # If we reach the bottom of maze, we can only move right
    if currRow==(endRow-1):
        # Completes the remainder of the path until it hits the end point
        for k in range(currCol,endCol):
            path[indx+k-currCol] = (currRow,k)
        # Calculates the maximum displacement for the current path
        D_curr = max([abs( elem[1]/endCol - elem[0]/endRow ) for elem in path])
        # Append this new displacement to a list of all other found displacements
        D_list.append(D_curr)
        return

    # If we reach to the right most corner, we can only move down
    if currCol == (endCol-1):
        # Completes the remainder of the path until it hits the end point
        for k in range(currRow,endRow):
            path[indx+k-currRow] = (k,currCol)
        # Calculates the maximum displacement for the current path
        D_curr = max([abs( elem[1]/endCol - elem[0]/endRow ) for elem in path])
        # Append this new displacement to a list of all other found displacements
        D_list.append(D_curr)
        return

    # This is activated any time we have not yet hit one of the walls
    else:
        # add Current coordinate to the path list
        path[indx]=(currRow,currCol)
        findPathsUtil(endRow, endCol, currRow+1, currCol, path, indx+1)
        findPathsUtil(endRow, endCol, currRow, currCol+1, path, indx+1)

if __name__ == '__main__':

    # Initialize cell array to consider
    startRow = 0
    startCol = 0
    endRow = 3
    endCol = 3

    global D_list
    D_list = []

    # First find all displacements for all possible paths are store in global variable D_list
    findPaths(startRow,startCol,endRow+1,endCol+1)

Я понимаю, что сетка 30 на 30 имеет невероятно большое количество возможных путей, связанных с ней, но все вещи, которые рассматриваются, есть программы, которые считают сетки намного более крупными,Есть ли способ резко сократить временную сложность этого расчета?Любые мысли или советы будут высоко оценены.