Find the minimum sum of a falling path in a square grid where two consecutive cells cannot be in the same column.
Given an grid of integers, choose one cell from each row so that the chosen cells form a falling path from top to bottom. For every pair of consecutive rows, the two chosen cells must be in different columns. The score of a path is the sum of its chosen values.
Return the minimum possible score.
A valid path picks exactly one cell from each row, and the column used in row must be different from the column used in row .
Input Format
- A square integer matrix
gridof sizen x n. grid[r][c]is the value of the cell in rowr, columnc.
Output Format
- Return a single integer: the minimum possible sum of a valid falling path.
Constraints
- The grid is square: .
- Choose exactly one cell from each row.
- Adjacent chosen cells in consecutive rows must not share the same column.
- Use 64-bit-safe accumulation if needed.
Example 1
Input
grid = [[1,2,3],[4,5,6],[7,8,9]]
Output
13
Explanation
One optimal path is 1 -> 5 -> 7, using columns 0, 1, 0. The sum is 13.
Example 2
Input
grid = [[7]]
Output
7
Explanation
There is only one cell, so the minimum path sum is 7.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.