记录矩阵中最小和路径所走的步数

Question

假设我有一个矩阵[[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]])

我该怎么做?

Answer 1

尝试以下递归方法:

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'])