All problems

Minimum Falling Path Sum

Medium · dynamic programming

A square board has n rows and n columns. Each cell holds a score, which may be negative.

A marble is dropped onto any cell of the top row. It then falls one row at a time. From the cell in column j, it lands in the next row in column j - 1, j or j + 1, as long as that column exists. It stops once it reaches the bottom row.

The total of a fall is the sum of the scores of every cell the marble touches, including the first and the last. Return the smallest total over every possible fall, from any starting cell in the top row.

Examples

Example 1

Input: matrix = [[2, 1, 3], [6, 5, 4], [7, 8, 9]]

Output: 13

Starting at 1, falling to 5 and then to 7 gives 1 + 5 + 7 = 13. No fall is cheaper.

Example 2

Input: matrix = [[-19, 57], [-40, -5]]

Output: -59

Starting at -19 and falling straight down to -40 gives -59.

Example 3

Input: matrix = [[8]]

Output: 8

A one-cell board has one fall: the marble starts and stops on the same cell.

Constraints