Minimum Falling Path Sum

Minimum falling path sum finds the cheapest path from the top row to the bottom, where each step moves down to the cell directly below or diagonally adjacent. A greedy that always takes the cheapest next cell fails, because a cheap cell can lead into an expensive region. Every path must be considered, but the paths overlap heavily — many share the same cells — and that overlap is what a DP exploits. The state is direct: - dp[i][j] is the minimum sum of any falling path ending at cell (i, j), built from the three cells that can reach it. So dp[i][j] = matrix[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]), considering only the neighbours that exist. The edge columns are where implementations break. Column 0 has no upper-left neighbour and the last column has no upper-right, so those terms must be excluded rather than read. Reading them either throws an index error or, worse in languages that wrap negative indices, silently reads from the opposite side of the row and produces a wrong answer that looks plausible. The first row needs no computation — a path ending there is just the cell's own value. The answer is the minimum across the entire bottom row, since a path may end at any column. Returning dp[n-1][0] or the last cell is a common slip. Only the previous row is ever read, so the table collapses to a single row and O(n) space. The matrix can also be modified in place for O(1) extra space when mutating the input is acceptable.

Row-by-row DP where each cell draws from the three cells diagonally above and directly above. Only the previous row matters, so one array rolls forward. The answer is the minimum over the final row, not a fixed corner.