如何在矩阵最小路径和DP求解过程中记录具体移动路径步骤

核心思路 #

你原有DP计算最小路径和的逻辑不需要改动，只需要在DP表计算完成后增加反向回溯步骤即可：

• 从右下角终点坐标(M-1, N-1)开始，往左上角起点(0,0)倒推每一步的来源
• 每一步判断当前DP值的来源是上方单元格还是左侧单元格，对应记录正向移动的动作
• 倒推完成后反转记录的动作列表，即可得到从起点到终点的完整正向路径

完整实现代码 #

mat_tr = [[1, -2, 3], [1, 2, 4], [2, 1, 6]]
M = len(mat_tr)
N = len(mat_tr[0])
new_tr = [[0]*N for _ in range(M)]

# 原有DP计算逻辑不变
new_tr[0][0] = mat_tr[0][0]
for j in range(1, N):
    new_tr[0][j] = mat_tr[0][j] + new_tr[0][j - 1]
for i in range(1, M):
    new_tr[i][0] = mat_tr[i][0] + new_tr[i - 1][0]
for i in range(1, M):
    for j in range(1, N):
        new_tr[i][j] = min(new_tr[i - 1][j], new_tr[i][j - 1]) + mat_tr[i][j]

# 新增反向回溯路径逻辑
i, j = M-1, N-1
reverse_path = []
while i > 0 or j > 0:
    if i == 0:
        # 已经到第一行，只能是从左边来的，对应正向动作right
        reverse_path.append('right')
        j -= 1
    elif j == 0:
        # 已经到第一列，只能是从上面来的，对应正向动作down
        reverse_path.append('down')
        i -= 1
    else:
        if new_tr[i][j] - mat_tr[i][j] == new_tr[i-1][j]:
            # 来源是上方，正向动作是down
            reverse_path.append('down')
            i -= 1
        else:
            # 来源是左方，正向动作是right
            reverse_path.append('right')
            j -= 1

# 反转得到正向路径
path = reverse_path[::-1]
print(path) # 输出：['right', 'down', 'down', 'right']
print('最小路径和为', new_tr[M-1][N-1]) # 输出：8

注意事项 #

• 如果矩阵中存在多个路径对应相同的最小和，上述逻辑会优先选择down方向的路径，如果需要优先选right，只需要把判断来源的if else条件调换顺序即可
• 该方法时间复杂度和原有DP逻辑一致，为O(M*N)，空间复杂度如果不需要保留DP表可以优化，一般场景下直接保留DP表即可

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