mediumDynamic Programming 2DPure DSA~20 min
Minimum Falling Path Through a Cost Grid
A signal descends a grid of stage costs one row at a time, each step moving straight down or diagonally to an adjacent column. Find the cheapest top-to-bottom descent.
Problem
Given an n x n integer matrix, return the minimum sum of a falling path: start at any cell in the first row and, from a cell (r, c), move to (r+1, c-1), (r+1, c), or (r+1, c+1) within bounds, ending at any cell in the last row.
Input
An n x n integer matrix (values may be negative).
Output
An integer: the minimum falling-path sum.
Constraints
- 1 <= n <= 100
- -100 <= matrix[i][j] <= 100
Examples
Example 1
Input
matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output
13
1 -> 5 -> 7 sums to 13.
Example 2
Input
matrix = [[-19,57],[-40,-5]]
Output
-59
-19 -> -40 sums to -59.