有没有更有效的方法来计算网格中所有可能路径的位移？

Question

我正在尝试用Python编写一个算法，它可以计算并存储n×m网格中所有可能路径的最大位移。没有障碍。我们从原点开始，每次可以向上或向右移动一个单位长度的网格。对于每个路径，我计算最大位移（使用预定义的公式），然后将该位移附加到列表中，以便在程序完成后可以访问它

我可以毫无问题地计算每条路径的最大位移，并且我已经实现了我的解决方案，这样只保存计算结果，因为没有这个，RAM就会过载。当网格大小为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的网格有大量与之相关联的可能路径，但是考虑到所有的事情，有些程序认为网格要大得多。有没有什么方法可以大大降低这种计算的时间复杂度？如有任何想法或建议，我们将不胜感激