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 .
grid of size n x n.grid[r][c] is the value of the cell in row r, column c.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
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.