获取最小总和路径动态规划方法索引的最佳方法？

Question

上下文：https://leetcode.com/problems/minimum-path-sum/

此问题的动态规划解决方案如下所示：

from math import inf

def min_path(grid, y, x):

    matrix = [[0] * (y + 1) for _ in range(x + 1)]
    matrix[0][0] = grid[0][0]

    for i, row in enumerate(matrix):
        for j, n in enumerate(row):
            if i == 0 and j == 0: 
               continue
            matrix[i][j] = grid[i][j] + min(i and matrix[i-1][j] or inf, j and matrix[i][j-1] or inf) 

    return matrix[x][y]

print(min_path([[1, 2, 3], 
                [4, 8, 2], 
                [1, 5, 3]], 2, 2))

但是，这种方法只returnslowest/largest求和路径。是否有一种简洁的方法也可以获取构成最佳路径的数字的实际索引？

Answer 1

将当前路径保留为元组的第二个元素。请注意，min() 的比较将由第一个元素执行，因此不应指定其他键。同样对于当前的问题，我们可以省略 tuple(tuple())，因为由于使用的算法，我们永远不会得到这个元素作为结果。我创建了一个按元素添加元组的函数，您也可以改用 numpy 数组或创建 lambda 函数并传递它而不是像 (lambda x,y: tuple(x[i]+y[i] for i in range(len(x))))(...).

这样的名称

from math import inf

def elwise(x,y):
    return tuple(x[i]+y[i] for i in range(len(x)))

def min_path(grid, y, x):
    matrix = [[(0, ((i,j),)) 
        for j in range(y + 1)] 
        for i in range(x + 1)]
    matrix[0][0] = (grid[0][0], ((0,0),))

    for i, row in enumerate(matrix):
        for j, n in enumerate(row):
            if i == j == 0: 
               continue
            matrix[i][j] = elwise(
                min(
                    i and matrix[i-1][j] or (inf,tuple(tuple())), 
                    j and matrix[i][j-1] or (inf,tuple(tuple()))), 
                (grid[i][j],((i,j),)))

    return matrix[x][y]

print(min_path([[1, 2, 3], 
                [4, 8, 2], 
                [1, 5, 3]], 2, 2))

此代码打印以下内容：

(11, ((0, 0), (0, 1), (0, 2), (1, 2), (2, 2)))

获取最小总和路径动态规划方法索引的最佳方法？

Best way to get the indexes of a minimum sum path dynamic programming approach?

python

algorithm

dynamic-programming