• 1 ≤ n ≤ 100
• The grid is square: n rows and n columns
• -100 ≤ matrix[i][j] ≤ 100
• From column c you may move to column c - 1, c or c + 1 in the row below

You drop through a square grid, one row at a time. From a cell you may step to the cell below, or diagonally below-left, or diagonally below-right — a column change of at most one. You may start on any cell of the top row, and you want the falling path with the smallest sum.

Two details drive the solution:

The start is free. Since any top-row cell is a valid start, the answer is the best over all cells of the top row, not a single fixed cell. So the final step is a minimum across a whole row.

Three choices per step, and edges exist. Down-left, straight down, down-right — three moves, not two. And near the left or right wall, some of those moves fall off the grid, so we must handle the boundary.

Values can be negative, so there is no "stop early, the sum only grows" shortcut — every path must be judged on its full sum.

The greedy idea — always step onto the smallest neighbour below — breaks for the usual reason. Consider

 1   99  99
 1   99  99
 1    1   1

Starting from any cell and always stepping to the smallest available neighbour keeps you in the left column, giving 1 + 1 + 1 = 3, which is right here. Now make the bottom-left cell 99 instead:

 1   99  99
 1   99  99
99    1   1

Greedy still walks the left column and is then forced onto 99 or 1 — it lands on the 1 at column 1, total 1 + 1 + 1 = 3. Fine. But swap so the middle column is cheap late and expensive early and you can always build a case where the cheap early column dead-ends. The general point stands: the cheapest next cell is not the cheapest next cell to be standing on, because what matters is the cost of the whole remaining descent, not the single step.

Where you are is a row and a column, and nothing about your history affects the rest of the fall.

Three children, take the cheapest:

f(r, c) = matrix[r][c] + min( f(r+1, c-1), f(r+1, c), f(r+1, c+1) )

with any out-of-range child ignored.

Base case: on the last row there is nowhere further to fall, so f(n-1, c) = matrix[n-1][c].

The answer is min over all c of f(0, c).

def min_falling_path_sum(matrix):
    n = len(matrix)
    INF = float('inf')
    memo = {}

    def f(r, c):
        if c < 0 or c >= n: return INF          # off the side of the grid
        if r == n - 1: return matrix[r][c]
        if (r, c) in memo: return memo[(r, c)]
        memo[(r, c)] = matrix[r][c] + min(f(r + 1, c - 1),
                                          f(r + 1, c),
                                          f(r + 1, c + 1))
        return memo[(r, c)]

    return min(f(0, c) for c in range(n))

There is one state per cell, so O(N²) time.

Now the table. Let dp[r][c] hold what f(r, c) returned, and swap calls for reads:

dp[r][c] = matrix[r][c] + min( dp[r+1][c-1], dp[r+1][c], dp[r+1][c+1] ) — any read off the grid counts as infinity.

Each cell reads the row r+1 below it, so fill bottom to top. The base case copies from the recursion: the last row has no row below, so dp[n-1][c] = matrix[n-1][c] — start the table as a copy of the bottom row. The answer is the smallest value in the top row, min(dp[0]):

def min_falling_path_sum(matrix):
    n = len(matrix)
    INF = float('inf')
    dp = [row[:] for row in matrix]             # last row is already correct

    for r in range(n - 2, -1, -1):
        for c in range(n):
            left  = dp[r + 1][c - 1] if c > 0     else INF
            mid   = dp[r + 1][c]
            right = dp[r + 1][c + 1] if c < n - 1 else INF
            dp[r][c] = matrix[r][c] + min(left, mid, right)

    return min(dp[0])

Note the very last line: min(dp[0]), not dp[0][0]. Forgetting that the start is free is the single most common wrong answer here, and it produces a result that is correct-looking but too large.

Row r reads only row r+1, so keep one array — but this time you cannot safely overwrite in place, because computing dp[c] needs dp[c-1] from the lower row, and sweeping left to right would have already destroyed it. Either sweep into a fresh array, or remember the value you overwrote:

def min_falling_path_sum(matrix):
    n = len(matrix)
    INF = float('inf')
    below = matrix[-1][:]

    for r in range(n - 2, -1, -1):
        current = [0] * n
        for c in range(n):
            left  = below[c - 1] if c > 0     else INF
            right = below[c + 1] if c < n - 1 else INF
            current[c] = matrix[r][c] + min(left, below[c], right)
        below = current

    return min(below)

Why can't we overwrite in place here? Because a cell reads dp[c-1], which sits behind the write position — a left-to-right sweep would already have destroyed it. Before compressing any table in place, check whether every value you read sits at or ahead of the cell you are writing. If it does not, use a second array.

Row 1 [6, 5, 4]:
- c=0: 6 + min(INF, 7, 8) = 6 + 7 = 13
- c=1: 5 + min(7, 8, 9) = 5 + 7 = 12
- c=2: 4 + min(8, 9, INF) = 4 + 8 = 12
→ [13, 12, 12]

Row 0 [2, 1, 3]:
- c=0: 2 + min(INF, 13, 12) = 2 + 12 = 14
- c=1: 1 + min(13, 12, 12) = 1 + 12 = 13
- c=2: 3 + min(12, 12, INF) = 3 + 12 = 15
→ [14, 13, 15]

Answer min(14, 13, 15) = 13, along 1 → 4 → 8 (columns 1 → 2 → 1). Notice the path drifts right and then back left — no monotonic rule would find it.

A single-cell grid [[-5]] returns -5 immediately from the base case, with no falling at all.

Three portable lessons sit in this problem.

When the start is free, the answer is an aggregate over a whole row of the table, not a single cell. Any time a problem says "starting from any X", expect a final min or max sweep over all the valid ends.

Use the right neutral value for out-of-range and impossible states. Infinity for a minimum, negative infinity for a maximum, zero for a count, false for a feasibility check. Choosing the wrong one produces silent wrong answers rather than crashes, which is far worse.

Check the read pattern before compressing memory. Reads that reach backwards forbid an in-place sweep. This one check would prevent a large share of the subtle bugs people hit when optimising these tables.