Minimum falling path through a matrix
Asked at IMC, Optiver
Start on any cell in the top row of a matrix. Each step moves down one row into the same column or a diagonally adjacent column (left or right). End on any cell in the bottom row, summing every cell you land on.
matrix = [[2, 1, 3],
[6, 5, 4],
[7, 8, 9]]
-> 13 # 1 -> 4 -> 8
Return the minimum falling-path sum. Aim for .
Show a hint
A cell in row r, column c can be reached from row r-1 at column c-1, c, or c+1. The cheapest way to stand on it is its own value plus the cheapest reachable cell above.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.