Minimum Path Sum

Problem

Return the minimum sum of a path from the top-left to the bottom-right of a grid of non-negative numbers, moving only right or down.

Fill a DP table where the first row and column accumulate directly and every other cell adds the smaller of its top and left neighbours. Return 0 for an empty grid.

Hint

Each cell's best path comes from the cheaper of the cell above and the cell to the left.

Test cases

case 1

in: [[[1,3,1],[1,5,1],[4,2,1]]]

expected: 7

case 2

in: [[[1,2],[3,4]]]

expected: 7

case 3

in: [[[5]]]

expected: 5

case 4

in: [[]]

expected: 0

case 5

in: [[[1,2,3]]]

expected: 6

Starter codePython

def min_path_sum(grid):
    # Your code here
    pass

5 test cases · run your code against them in the editor