如何获取矩阵中从左上到右下的最大和路径坐标（仅允许向右或向下移动）

嘿，这个需求很实用！你现有的max_path函数已经完美计算出了最大路径和，现在只需要在动态规划的过程中额外记录每个位置的来源方向，最后通过回溯就能得到具体的路径坐标啦。我来给你调整一下代码：

修改后的完整代码 #

def max_path_with_coords(grid):
    N = len(grid)
    if N == 0:
        return 0, []
    M = len(grid[0])
    # sum_dp矩阵：记录到每个位置(i,j)的最大路径和（1-based索引）
    sum_dp = [[0]*(M+1) for _ in range(N+1)]
    # parent矩阵：记录每个位置的来源方向，'up'表示从上方来，'left'表示从左方来
    parent = [[None]*(M+1) for _ in range(N+1)]
    
    for i in range(1, N+1):
        for j in range(1, M+1):
            if i == 1 and j == 1:
                # 起点位置，直接赋值
                sum_dp[i][j] = grid[i-1][j-1]
                parent[i][j] = None
            elif i == 1:
                # 第一行只能从左侧移动过来
                sum_dp[i][j] = sum_dp[i][j-1] + grid[i-1][j-1]
                parent[i][j] = 'left'
            elif j == 1:
                # 第一列只能从上方移动过来
                sum_dp[i][j] = sum_dp[i-1][j] + grid[i-1][j-1]
                parent[i][j] = 'up'
            else:
                # 比较上方和左方的路径和，选择更大的那个作为来源
                if sum_dp[i-1][j] > sum_dp[i][j-1]:
                    sum_dp[i][j] = sum_dp[i-1][j] + grid[i-1][j-1]
                    parent[i][j] = 'up'
                else:
                    sum_dp[i][j] = sum_dp[i][j-1] + grid[i-1][j-1]
                    parent[i][j] = 'left'
    
    # 回溯获取路径：从终点往起点走，最后反转得到正序路径
    path = []
    i, j = N, M
    while i > 0 and j > 0:
        # 转换为原矩阵的0-based坐标
        path.append((i-1, j-1))
        if parent[i][j] == 'up':
            i -= 1
        elif parent[i][j] == 'left':
            j -= 1
        else:
            # 到达起点，终止循环
            break
    path.reverse()
    
    return sum_dp[N][M], path

测试你的例子 #

matrix = [[1, 2, 3], [3, 4, 5]]
max_sum, path = max_path_with_coords(matrix)
print(f"最大路径和：{max_sum}")
print(f"路径坐标：{path}")

运行后输出：

最大路径和：13
路径坐标：[(0, 0), (1, 0), (1, 1), (1, 2)]

关键逻辑说明 #

• 路径记录：新增的parent矩阵用来标记每个位置的移动来源，这样我们就能从终点反向推导回起点。
• 边界处理：第一行和第一列的位置只能从单一方向移动过来，所以直接标记对应的来源方向，避免逻辑错误。
• 回溯反转：因为我们是从终点往起点回溯的，所以最后需要把路径反转，才能得到从左上角到右下角的正确顺序。

如果你的矩阵存在多条最优路径（即上方和左方的路径和相等），当前代码会优先选择左方的路径。如果需要收集所有最优路径，可以把parent改成存储所有可能的来源方向，再通过递归遍历所有路径~

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