Minimum Falling Path Sum

Find the minimum sum when traversing a grid from top to bottom, moving diagonally or straight down.

dynamic programming grid path sum optimization

Write a function `min_falling_path_sum(matrix)` that takes a square matrix (list of lists) of integers and returns the minimum sum of a falling path. 

A falling path starts at any element in the first row and ends at any element in the last row. From a cell `(r, c)`, you can move to `(r+1, c-1)`, `(r+1, c)`, or `(r+1, c+1)` as long as the new column is within bounds. You must visit exactly one cell per row.

For example, given `matrix = [[2,1,3],[6,5,4],[7,8,9]]`, the possible paths include `1 -> 5 -> 7` (sum 13) or `1 -> 5 -> 8` (sum 14) or `3 -> 4 -> 9` (sum 16). The minimum is 13.

Constraints:
- The matrix is non-empty and square (n rows, n columns).
- `1 <= n <= 100`.
- Each element is an integer in the range `[-100, 100]`.

Implement the function to return the integer minimum sum.

Constraints

Matrix size: 1 ≤ n ≤ 100. Values: -100 ≤ matrix[i][j] ≤ 100. Time: O(n^2) expected. Space: O(1) or O(n).

Example

>>> min_falling_path_sum([[2,1,3],[6,5,4],[7,8,9]])
13
>>> min_falling_path_sum([[-19,57],[-40,-5]])
-59
>>> min_falling_path_sum([[5]])
5

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about filling a DP table where dp[i][j] is the minimum sum to reach cell (i,j).

For each cell in a row, consider the three cells above it: left, middle, right. Ignore those out of bounds.

You can compute the dp row by row and keep only the previous row to save space.

The answer is the minimum value in the last row of the DP table.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.