Just wonder if they require us to output the steps of the route?


  • 0
    L

    Now we only have to output the minimum sum, but actually we don't know how we move from the start to the end.
    How to do it if we are required to give every step of that minimum route?


  • 0
    M

    Actually we exactly know the steps, all we need to do is to track the selection of the previous step either from top or left. For every node in the grid, memorize the selection when calculating the min path, and finally you could know the whole path by looking from the right bottom corner node.

    For a better understanding, you can look the code to know how the path will be displayed:

    import sys
    
    class Solution(object):
        def minPathSum(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            m = len(grid)
            if m == 0:
                return 0
            n = len(grid[0])
            if n == 0:
                return 0
            path = [sys.maxint] * (n + 1)
    
            for i in range(m):
                if i == 0:
                    path[0] = 0
                else:
                    path[0] = sys.maxint
                for j in range(n):
                    if path[j] <= path[j + 1]:
                        print "%d, pick %s" % (grid[i][j], "left"),
                    else:
                        print "%d, pick %s" % (grid[i][j], "top "),
                    path[j + 1] = min(path[j], path[j + 1]) + grid[i][j]
                    if j == n - 1:
                        print ""
    
            return path[n]
    

    Try to run the code and see what happens.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.