grid is an n × n grid of integers, and some of them may be negative. A falling path starts on any cell of the top row and drops one row at a time until it reaches the bottom row. From cell (r, c) it moves to (r + 1, c - 1), (r + 1, c) or (r + 1, c + 1): straight down, or down one column to the left or right, staying inside the grid. Its sum is the total of the n cells it visits.
Write min_falling_path_sum(grid: list[list[int]]) -> int: the smallest sum any falling path can have.
Examples:
grid = [[4, 7, 3, 6],
[2, 9, 5, 2],
[8, 1, 6, 3],
[5, 4, -2, 7]]
min_falling_path_sum(grid) == 5: 4 → 2 → 1 → -2. Starting on the smallest top cell, 3, can't do better than 6 (3 → 2 → 3 → -2).
min_falling_path_sum([[-4]]) == -4min_falling_path_sum([[2, 3], [4, -6]]) == -4:2 → -6.
Constraints: 1 <= n <= 500, values -100..100.
⭐ Bonus: a speed test on a 500 x 500 grid earns a star in O(n²). Each step has up to three choices, so the number of paths grows like 3ⁿ and trying them all is hopeless there.
Show hint
the cheapest way to reach a cell only depends on the cheapest ways to reach the three cells above it.