minimum_path_sum.py

defmin_path_sum(grid: list) ->int:
"""
 Find the path from top left to bottom right of array of numbers
 with the lowest possible sum and return the sum along this path.
 >>> min_path_sum([
 ... [1, 3, 1],
 ... [1, 5, 1],
 ... [4, 2, 1],
 ... ])
 7

 >>> min_path_sum([
 ... [1, 0, 5, 6, 7],
 ... [8, 9, 0, 4, 2],
 ... [4, 4, 4, 5, 1],
 ... [9, 6, 3, 1, 0],
 ... [8, 4, 3, 2, 7],
 ... ])
 20

 >>> min_path_sum(None)
 Traceback (most recent call last):
 ...
 TypeError: The grid does not contain the appropriate information

 >>> min_path_sum([[]])
 Traceback (most recent call last):
 ...
 TypeError: The grid does not contain the appropriate information
 """

ifnotgridornotgrid[0]:
raiseTypeError("The grid does not contain the appropriate information")

forcell_ninrange(1, len(grid[0])):
grid[0][cell_n] +=grid[0][cell_n-1]
row_above=grid[0]

forrow_ninrange(1, len(grid)):
current_row=grid[row_n]
grid[row_n] =fill_row(current_row, row_above)
row_above=grid[row_n]

returngrid[-1][-1]


deffill_row(current_row: list, row_above: list) ->list:
"""
 >>> fill_row([2, 2, 2], [1, 2, 3])
 [3, 4, 5]
 """

current_row[0] +=row_above[0]
forcell_ninrange(1, len(current_row)):
current_row[cell_n] +=min(current_row[cell_n-1], row_above[cell_n])

returncurrent_row


if__name__=="__main__":
importdoctest

doctest.testmod()