求解nxn矩阵从(0,0)到(n,n)仅右上移动的最大路径和及对应路径实现问题

现有代码的基础问题修正 #

• 方向描述笔误：从(0,0)（矩阵左上角）出发到(n,n)（矩阵右下角），仅允许向下、向右移动，不存在向上、向左移动的合法路径（否则会跑出矩阵边界），你现有动态规划的计算逻辑本身匹配这个移动规则，只是方向描述写错了。
• 硬编码尺寸问题：你写死了m=3、n=3，更换输入矩阵尺寸后会直接引发索引错误，应该根据输入矩阵的实际行数、列数自动计算边界。
• DP循环变量名误导：你在非边界单元格的计算代码中，把正上方的累加和赋值给了叫left的变量、把正左方的累加和赋值给了叫below的变量，虽然取最大值时结果没有错，但命名和实际逻辑相反，很容易在回溯路径时搞反判断方向。

路径获取的核心逻辑 #

你已经构建好的maxPath矩阵，存储了到达每个坐标点的最大元素累加和，不需要额外增加复杂计算，只要从终点反向回溯到起点，就能还原完整最优路径：

• 对当前位置(i,j)，对比它正上方相邻单元格(i-1,j)的最大累加和、正左方相邻单元格(i,j-1)的最大累加和
• 哪个相邻单元格的累加和更大，就说明最优路径是从那个方向走到当前位置的，把当前位置加入路径列表后，移动到那个相邻位置继续回溯
• 一直走到起点(0,0)停止，将最终的路径列表反转，就是从起点到终点的正向最优路径

修正后可同时输出最大和、对应路径的完整代码 #

# Forming a matrix
mat=[[0,0,20,4],
     [4,5,3,6],
     [1,3,5,2],
     [50,4,6,0]]

def maxPath(matrix):
    # 自动识别矩阵尺寸，替代硬编码
    m = len(matrix) - 1
    n = len(matrix[0]) - 1
    
    # 初始化DP矩阵：存储每个位置能获得的最大累加和
    maxPath = [[0 for x in range(n+1)] for y in range(m+1)]
    
    # 初始化起点的累加和
    maxPath[0][0] = matrix[0][0]
    
    # 计算第一列的累加和（第一列只能从上往下走）
    for i in range(1, m+1):
        maxPath[i][0] = maxPath[i-1][0] + matrix[i][0]
    
    # 计算第一行的累加和（第一行只能从左往右走）
    for j in range(1, n+1):
        maxPath[0][j] = maxPath[0][j-1] + matrix[0][j]
    
    # 计算其余位置的最大累加和
    for i in range(1, m+1):
        for j in range(1, n+1):
            top_val = maxPath[i-1][j]
            left_val = maxPath[i][j-1]
            maxPath[i][j] = matrix[i][j] + max(top_val, left_val)
    
    # 反向回溯还原路径
    path = []
    curr_i, curr_j = m, n
    while True:
        path.append((curr_i, curr_j))
        # 回到起点就终止回溯
        if curr_i == 0 and curr_j == 0:
            break
        # 已在第一行，只能往左回溯
        if curr_i == 0:
            curr_j -= 1
        # 已在第一列，只能往上回溯
        elif curr_j == 0:
            curr_i -= 1
        # 普通位置：选累加和更大的方向回溯
        else:
            if maxPath[curr_i-1][curr_j] > maxPath[curr_i][curr_j-1]:
                curr_i -= 1
            else:
                curr_j -= 1
    # 反转得到从起点到终点的正向路径
    path.reverse()
    
    return maxPath[m][n], path

highestSumPath, path = maxPath(mat)
print("Highest-sum is: ", highestSumPath)
print("对应路径坐标为: ", path)
print("路径经过的元素值为: ", [mat[i][j] for i,j in path])

针对你给出的测试矩阵，运行后得到的最大和为65，对应路径经过的元素依次是0、4、1、50、4、6、0，累加值匹配最优结果。

内容的提问来源于stack exchange，提问作者Said Yeginoglu