555. Minimum Falling Path Sum
You receive an n × n grid of integers matrix. A falling path starts at any cell of the top row and drops one row per step: from a cell in column c it may land in the next row at column c − 1, c, or c + 1 (never leaving the grid), until it reaches the bottom row.
Return the smallest possible sum of the values along a falling path.
Both the starting column and every step are yours to choose — the question is how to search all of those choices without enumerating every path.
Example 1:
Input: matrix = [[2, 8, 4], [9, 3, 7], [6, 5, 1]]
Output: 6
Explanation: Start at 2 (top-left), fall diagonally to 3, then diagonally again to 1: 2 + 3 + 1 = 6. No other falling path sums lower.
Example 2:
Input: matrix = [[1, 2], [3, 4]]
Output: 4
Explanation: Start at 1 and drop straight down to 3: 1 + 3 = 4.
Constraints:
- 1 ≤ n ≤ 100
- -100 ≤ matrix[i][j] ≤ 100
Hints:
A path makes a choice at every row, so there are up to 3^(n−1) paths from each start — too many to try. But how many distinct (row, column) positions are there?
Define best(r, c) = the cheapest falling path that ends at cell (r, c). A path can only arrive from the three cells above it, so best(r, c) = matrix[r][c] + min of the three best values in row r − 1. Fill row by row; the answer is the minimum of the last row.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: matrix = [[2, 8, 4], [9, 3, 7], [6, 5, 1]]
Expected output: 6