Minimum Falling Path Sum
Find the minimum sum path falling from the top row to the bottom row, moving straight down or one column diagonally each step.
Open on LeetCode ↗Intuition
The trap is forgetting that the diagonal moves are bounded at the edges. Column 0 has no upper-left parent to fall from, and the last column has no upper-right parent -- an unguarded min() over three fixed parent offsets either reads past the array bounds or, worse, silently wraps around and compares against the wrong side of the row entirely. The fix is to only include parents that actually exist: for column j, gather dp[j] always, dp[j-1] only if j-1 >= 0, and dp[j+1] only if j+1 < n. The invariant: dp[j] after processing row i is the minimum sum of a falling path that ends at column j in row i, built strictly from in-bounds parents in the row above.
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.
Approach
Seed with the top row
dp starts as a copy of row 0 -- a path of length one that ends at each column simply costs that cell's own value.
Fill downward with guarded neighbors
For each row i from 1 to n-1, and each column j, collect the candidate parent values: dp[j] (straight down, always valid), dp[j-1] (only if j > 0), and dp[j+1] (only if j < n-1). Take the minimum of whichever candidates exist and add matrix[i][j].
Read the last row
After processing the final row, the answer is the minimum value across that row's dp -- the cheapest path could end at any column.
Solution & live demo
Common pitfalls
Overwriting the row in place
for j in range(n):
dp[j] = matrix[i][j] + min(dp[j-1], dp[j], dp[j+1])new_dp = [0] * n ... dp = new_dp
Writing dp[j] destroys the value that dp[j+1]'s computation still needs — the neighbour to its left. Either use a fresh array or save the overwritten value before moving on.
Returning dp[0]
return dp[0]
return min(dp)
A falling path may end at any column of the last row. Reading a single position reports one particular path rather than the cheapest available.
Not guarding the column edges
min(dp[j-1], dp[j], dp[j+1])
if j - 1 >= 0: candidates.append(dp[j - 1]) if j + 1 < n: candidates.append(dp[j + 1])
Column 0 has no upper-left neighbour, and in Python dp[-1] silently wraps to the far end of the row — producing a legal-looking sum from a path that doesn't exist.
Edge cases
Only dp[0] and dp[1] are valid parents; dp[-1] is never included.
Only dp[n-2] and dp[n-1] are valid parents; dp[n] is never included.
The loop over rows never runs; the answer is the single cell's value.
min() still correctly finds the most negative total sum with no special handling needed.