grid is an n × n grid of integers, and some of them may be negative. Build a path by picking exactly one cell from every row, top to bottom. Any column is allowed, near or far, with one rule: the cells picked from two neighbouring rows must be in different columns. The path's sum is the total of the n picked cells.
Write min_falling_path_sum(grid: list[list[int]]) -> int: the smallest sum such a path can have.
Examples:
grid = [[4, 1, 6],
[3, 2, 7],
[5, 0, 9]]
min_falling_path_sum(grid) == 4: 1 → 3 → 0, in columns 1, 0, 1. The smallest cell of every row is in column 1, and 1 → 2 → 0 would sum to 3, but it stays in one column between neighbouring rows, so it isn't allowed.
min_falling_path_sum([[-5]]) == -5: one row, so the single cell is the whole path.min_falling_path_sum([[1, 2], [3, 4]]) == 5:1 → 4or2 → 3, never1 → 3.
Constraints: 1 <= n <= 600, values -99..99.
⭐ Bonus: a speed test on a 600 x 600 grid earns a star in O(n²). Checking every column of the row above for every cell is O(n³), about 200 million steps there, which is too slow in Python.
Show hint
for each cell you want the cheapest sum in the row above that isn't in your column. For all but one column that's the row's smallest sum. Which number does the remaining column need?