Minimum Falling Path Sum - Solution & Explanation

Problem Overview: You are given an n x n matrix of integers. A falling path starts at any cell in the first row and moves to the next row either directly below, diagonally left, or diagonally right. The goal is to compute the minimum possible sum of values along any valid falling path from the top row to the bottom row.

Approach 1: Top-Down Dynamic Programming with Memoization (Time: O(n^2), Space: O(n^2))

This approach models the problem as recursion over rows. For each cell (r, c), recursively compute the minimum path sum starting from that cell by exploring the three valid next positions: (r+1, c-1), (r+1, c), and (r+1, c+1). Many subproblems repeat, so store results in a memo table to avoid recomputation. Each cell is solved once, which reduces exponential recursion to quadratic time. This method is intuitive if you think in terms of exploring all paths but caching results.

The recursion stops when the last row is reached. Out-of-bound column moves are ignored. Because every matrix cell is computed once and stored, the complexity becomes O(n^2). This pattern is common in dynamic programming problems on grids.

Approach 2: Bottom-Up Dynamic Programming (Time: O(n^2), Space: O(n^2) or O(1) in-place)

The bottom-up strategy processes the matrix row by row. Starting from the second row, update each cell by adding the minimum of the three reachable cells from the previous row: up-left, up, and up-right. This converts the matrix into a DP table where each entry represents the minimum path sum reaching that cell.

For cell (r, c), compute matrix[r][c] += min(prev[c], prev[c-1], prev[c+1]) while handling boundary columns carefully. After processing all rows, the answer is the minimum value in the last row. This method iterates once over the grid and avoids recursion overhead. Because the DP values can overwrite the original matrix, the extra space can be reduced to O(1).

This technique is typical for problems involving transitions in a matrix or grid where each state depends on nearby cells. Iterating through the array structure row by row keeps the implementation simple and efficient.

Recommended for interviews: Bottom-up dynamic programming is the expected solution. It demonstrates that you can convert recursive state transitions into iterative DP and optimize space if needed. Showing the top-down memoized version first can help explain the recurrence, but the bottom-up implementation signals stronger DP problem-solving skills.