时间戳

首页 > 解决方案 > 记录矩阵中最小和路径所采取的步骤

python - 记录矩阵中最小和路径所采取的步骤

问题描述

假设我有一个矩阵 [[1, -2, 3], [1, 2, 4], [2, 1, 6]]，我必须找到从左上角到右下角总和最小的路径.

我使用了下面的 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]
        print(new_tr[i][j])

我想记录为获得最小总和而采取的每一步。（例如（右、下、下、右）在 [[1, -2, 3], [1, 2, 4], [2, 1, 6]] 的情况下）

我可以这样做的方法是什么？

标签： pythonmatrixdynamic-programming

解决方案

尝试以下递归方法：

mat = [[1, -2, 3], [1, 2, 4], [2, 1, 6]]

def smallest(mat, x=0, y=0):
    # mat: nested list for the matrix
    # x, y: current position
    # output: tuple (val, path)
    #         val: smallest value from the current position to the destination
    #         path: list. path to the destination
    rows, cols = len(mat), len(mat[0]) # size of the matrix
    if (x, y) == (rows - 1, cols - 1): # if arrived at the southeast corner
        return mat[x][y], []
    candidates = [] # store results from deeper calls
    if x < rows - 1: # if we can go down
        candidates.append([*smallest(mat, x + 1, y), 'down'])
    if y < cols - 1: # if we can go right
        candidates.append([*smallest(mat, x, y + 1), 'right'])
    candidate = min(candidates, key=lambda u: u[0]) # pick the smaller result
    return mat[x][y] + candidate[0], [candidate[2], *candidate[1]]

print(smallest(mat)) # (8, ['right', 'down', 'down', 'right'])

推荐阅读