Minimum Falling Path Sum

Given a nonempty rectangular integer matrix, return the smallest sum of a path starting at any cell of the first row and ending at any cell of the last row.…

Given a nonempty rectangular integer matrix, return the smallest sum of a path starting at any cell of the first row and ending at any cell of the last row. From a cell, move exactly one row down, either in the same column or one column left or right, staying inside the matrix. Include every visited cell, including the start and end. Return only the minimum sum.

- 1 <= number of rows, number of columns <= 100; rectangular matrices are allowed. - -1000 <= matrix[row][column] <= 1000. - Negative path sums are valid. These bounds imply a result between -100000 and 100000. - Visualizer presets use matrices at most 8 by 8; larger valid inputs are coding-only.

Example 1: input matrix = [[1,2,10,4],[100,3,2,1],[1,1,20,2],[1,2,2,1]]; output 6. One minimum route visits 1, 3, 1, 1.

Example 2: input matrix = [[1,4,3,1],[2,3,-1,-1],[1,1,-1,8]]; output -1. Start at the last cell of the top row, then visit -1 and -1.

Category: Arrays. Topic: dynamic-programming. Difficulty: medium. Patterns: dynamic-programming, dynamic-programming-2d.