如何修改Python程序输出矩阵左下角到右上角的最大代价路径

你当前的代码已经能计算从矩阵左下角到右上角的最大代价和，但缺少路径追踪功能。要实现路径输出，我们可以添加一个父节点记录矩阵，记录每个单元格的最优路径来源，最后从终点回溯到起点再反转得到完整路径。

修改后的完整代码 #

from collections import deque as queue
import random

array = []
def creatArray():
    x = 5
    y = 5
    global array
    for i in range(x):
        array.append([])
        for j in range(y):
            array[i].append(random.randint(0,100))
    return array
creatArray()

ROW = 5
COL = 5

# 检查坐标是否在矩阵范围内
def isValid(p):
    return (p[0] >= 0) and (p[0] < ROW) and (p[1] >= 0) and (p[1] < COL)

# 计算最大代价并追踪路径
def find_max_cost_and_path(mat):
    max_val = [[0 for _ in range(COL)] for _ in range(ROW)]
    # 父节点矩阵，记录每个单元格的来源坐标
    parent = [[None for _ in range(COL)] for _ in range(ROW)]

    # 起点初始化：左下角
    start_row, start_col = ROW - 1, 0
    max_val[start_row][start_col] = mat[start_row][start_col]

    q = queue()
    q.appendleft([start_row, start_col])

    while len(q) > 0:
        curr = q.pop()
        curr_row, curr_col = curr[0], curr[1]

        # 定义三个可行方向：上、右、右上
        directions = [
            [-1, 0],    # 上
            [0, 1],     # 右
            [-1, 1]     # 右上
        ]

        for dr, dc in directions:
            next_row = curr_row + dr
            next_col = curr_col + dc
            if isValid([next_row, next_col]):
                new_cost = max_val[curr_row][curr_col] + mat[next_row][next_col]
                # 如果新路径代价更大，更新最大值并记录父节点
                if new_cost > max_val[next_row][next_col]:
                    max_val[next_row][next_col] = new_cost
                    parent[next_row][next_col] = (curr_row, curr_col)
                    q.appendleft([next_row, next_col])

    # 从终点回溯到起点，构建路径
    path = []
    curr_row, curr_col = 0, COL - 1  # 终点：右上角
    while curr_row is not None and curr_col is not None:
        path.append(mat[curr_row][curr_col])
        next_parent = parent[curr_row][curr_col]
        if next_parent is None:
            break
        curr_row, curr_col = next_parent

    # 反转路径，得到从起点到终点的顺序
    path.reverse()
    return max_val[0][COL - 1], path

# 主程序
print("Given matrix is ")
for row in array:
    print(" ".join(map(str, row)))

max_cost, path = find_max_cost_and_path(array)
print(f"Maximum cost is  {max_cost}")
print(f"Way is {'-'.join(map(str, path))}")

关键修改说明 #

1. 父节点矩阵 parent：每个单元格存储到达它的最优路径的来源坐标，用于后续回溯路径。
2. 路径回溯逻辑：从右上角终点开始，通过parent矩阵一步步倒推回起点，再反转路径得到从左下角到右上角的顺序。
3. 方向遍历优化：把三个方向统一用列表管理，代码更简洁。
4. 边界检查修正：原isValid函数缺少行上限检查，现在补充完整，避免越界错误。

示例输出 #

Given matrix is
97 16 73 23 43
99 30 37 71 29
5 52 89 98 19
73 66 89 97 15
96 2 15 31 96
Maximum cost is  662
Way is 96-73-5-99-97-16-73-23-43

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