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?
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) if n == 0: return 0 path = [sys.maxint] * (n + 1) for i in range(m): if i == 0: path = 0 else: path = 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.